TAILIEUCHUNG - Báo cáo khoa học:Voltage Graphs, Group Presentations and Cages

The cage problem asks for the construction of regular graphs with specified degree and girth. Reviewing terminology, we recall that the girth of a graph is the length of a shortest cycle, that a (k, g)-graph is regular graph of degree k and girth g, and that a (k, g)-cage is a (k, g)-graph of minimum possible order. Define f(k, g) to be this minimum. We focus on trivalent (or cubic) cages. It is well known that. | Voltage Graphs Group Presentations and Cages Geoffrey Exoo Department of Mathematics and Computer Science Indiana State University Terre Haute IN 47809 g-exoo@ Submitted Dec 2 2003 Accepted Jan 29 2004 Published Feb 14 2004 Abstract We construct smallest known trivalent graphs for girths 16 and 18. One construction uses voltage graphs and the other coset enumeration techniques for group presentations. AMS Subject Classifications 05C25 05C35 1 Introduction The cage problem asks for the construction of regular graphs with specified degree and girth. Reviewing terminology we recall that the girth of a graph is the length of a shortest cycle that a k g -graph is regular graph of degree k and girth g and that a k g -cage is a k g -graph of minimum possible order. Define f k g to be this minimum. We focus on trivalent or cubic cages. It is well known that 29 2 1 if g is even 3 X 2 g-1 2 2 if g is odd This bound the Moore bound is achieved only for girths 5 6 8 and 12 1 4 . The problem of finding cages has been chronicled by Biggs 3 and others. In this note we give two new constructions of cage candidates using different methods. f 3 g I THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 N2 1 2 A Girth 16 Lift of the Petersen Graph The first and simplest of the constructions begins with the Petersen graph denoted P the smallest 3-regular graph of girth 5. We investigate graphs that can be constructed as lifts of the P and discover a new graph the smallest known trivalent graph of girth 16. Note that lift have been previously used with reference to the closely related degreediameter problem 9 . The graph has 960 vertices improving the old bound of 992 given in 2 . Our method is best described using voltage graph terminology first introduced by Gross 7 which we now review. If G is a finite graph denote its vertex and edge sets by V G and E G . Also let D G denote the set of arcs on G each edge e E E G is represented exactly twice in D G . with each of the two .

• Báo cáo khoa học
• Voltage Graphs
• Group Presentations
• Cages mathematical knowledge
• reports of mathematics
• mathematical works
• scientific reports
• scientific research
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học
• công trình toán học
• Research methods
• Data collection methods
• Understanding scientific research
• Ensuring research validity
• Measurement techniques
• Sampling methods
• Scientific research capacity
• Educational institutions
• Policy and management studies
• Vietnam Academy for Ethnic minorities
• Scientific bases
• earth sciences
• Research
• VNU Journal of Science
• Action research
• linguistics
• research projects
• Foreign Languages
• cooperative research
• Renewable energy
• Introduction to research
• Scientific investigation
• Scientific investigation research
• Experimental designs
• Measurement of variables
• Reading research
• Conducting and reading research
• Research process
• Research report
• Purpose of research
• Scientific method
• Conducting research
• The effect of university autonomy on training and scientific research
• Vietnam national university of agriculture
• Training and scientific research
• Vascular plant
• Flora
• Yen Tu
• Quang Ninh Research Forest
• statements and documents scientific reports
• medical reports
• medical knowledge
• medical research
• clinical trials
• medical management
• health care
• Methods in behavioral research
• Behavioral research
• Scientific understanding
• Fundamental research issues
• Measurement concepts
• Observational methods
• reading comprehension
• education
• optimal picket
• model creation
• urban expansion
• organizing spatial
• Journal of Science
• Journal of Technology
• Technology Management
• Research quality
• Strategy and policy
• Summary of Doctoral thesis
• Summary of Doctoral thesis in public Management
• State management
• Female scientific research human
• Research human resource development
• Scientific research and teaching
• Defense and security education
• Current situation and solutions
• Security education
• Structural biochemistry
• epigenetics
• MicroRNAs
• Tạp chí khoa học
• Tạp chí Công nghệ
• Quản lý công nghệ
• Human resources
• Science management
• Poliomyelitis vaccine Research
• Non Ri Maprec
• Production center