请输入您要查询的百科知识:

 

词条 Klein graphs
释义

  1. The cubic Klein graph

     Algebraic properties  Gallery 

  2. The 7-valent Klein graph

     Algebraic properties 

  3. References

In the mathematical field of graph theory, the Klein graphs are two different but related regular graphs, each with 84 edges. Each can be embedded in the orientable surface of genus 3, in which they form dual graphs.

The cubic Klein graph

{{infobox graph
| name = The (cubic) Klein graph
| image =
| image_caption = The 56-Klein graph
| namesake = Felix Klein
| vertices = 56
| edges = 84
| automorphisms= 336
| girth = 7
| radius = 6
| diameter = 6
| chromatic_number = 3
| chromatic_index = 3
| properties = Symmetric
Cubic
Hamiltonian
Cayley graph
|book thickness=3|queue number=2}}

This graph is a 3-regular graph with 56 vertices and 84 edges, named after Felix Klein.

It is a Hamiltonian graph. It has chromatic number 3, chromatic index 3, radius 6, diameter 6 and girth 7. It is also a 3-vertex-connected and a 3-edge-connected graph. It has book thickness 3 and queue number 2.[1]

It can be embedded in the genus-3 orientable surface (which can be represented as the Klein quartic), where it forms the "Klein map" with 24 heptagonal faces, Schläfli symbol {7,3}8.

According to the Foster census, the Klein graph, referenced as F056B, is the only cubic symmetric graph on 56 vertices which is not bipartite.[2]

It can be derived from the 28-vertex Coxeter graph.[3]

Algebraic properties

The automorphism group of the Klein graph is the group PGL2(7) of order 336, which has

PSL2(7) as a normal subgroup. This group acts transitively on its half-edges, so the Klein graph is a symmetric graph.

The characteristic polynomial of this 56-vertices Klein graph is equal to

Gallery

The 7-valent Klein graph

{{infobox graph
| name = The (7-valent) Klein graph
| image =
| image_caption = The 24-Klein graph
| namesake = Felix Klein
| vertices = 24
| edges = 84
| automorphisms= 336
| girth = 3
| radius = 3
| diameter = 3
| chromatic_number = 4
| chromatic_index = 7
| properties = Symmetric
Hamiltonian
}}

This graph is a 7-regular graph with 24 vertices and 84 edges, named after Felix Klein.

It is a Hamiltonian graph. It has chromatic number 4, chromatic index 7, radius 3, diameter 3 and girth 3.

It can be embedded in the genus-3 orientable surface, where it forms the dual of the "Klein map", with 56 triangular faces, Schläfli symbol {3,7}8.[4]

It is the unique distance-regular graph with intersection array ; however, it is not a distance-transitive graph.[5]

Algebraic properties

The automorphism group of the 7-valent Klein graph is the same group of order 336 as for the cubic Klein map, likewise acting transitively on its half-edges.

The characteristic polynomial of this 24-vertices Klein graph is equal to .[6]

References

1. ^Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
2. ^{{citation | last1 = Conder | first1 = M. | author1-link = Marston Conder | last2 = Dobcsányi | first2 = P. | journal = J. Combin. Math. Combin. Comput. | pages = 41–63 | title = Trivalent symmetric graphs up to 768 vertices | volume = 40 | year = 2002}}.
3. ^{{cite journal|last=Dejter|first=Italo|title=From the Coxeter graph to the Klein graph|publisher=CiteSeer|citeseerx=10.1.1.188.2580}}
4. ^{{cite journal |last1=Schulte |first1=Egon |last2=Wills |first2=J. M. |title=A Polyhedral Realization of Felix Klein's Map {3, 7}8 on a Riemann Surface of Genus 3 |journal=J. London Math. Soc. |year=1985 |volume=s2-32 |issue=3 |pages=539–547 |url=http://jlms.oxfordjournals.org/content/s2-32/3/539.abstract|doi=10.1112/jlms/s2-32.3.539 }}
5. ^{{cite book|last1=Brouwer|first1=Andries|author-link1=Andries Brouwer|last2=Cohen|first2=Arjeh|last3=Neumaier|first3=Arnold|title=Distance-Regular Graphs|publisher=Springer-Verlag|year=1989|isbn=978-0-387-50619-7|page=386}}
6. ^{{cite journal|last1=van Dam|first1=E. R.|last2=Haemers|first2=W. H.|last3=Koolen|first3=J. H.|last4=Spence|first4=E.|title=Characterizing distance-regularity of graphs by the spectrum|journal=J. Combin. Theory Ser. A|year=2006|volume=113|issue=8|pages=1805–1820|doi=10.1016/j.jcta.2006.03.008|url=http://www.sciencedirect.com/science/article/pii/S0097316506000574|accessdate=16 August 2016}}

2 : Individual graphs|Regular graphs

随便看

 

开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。

 

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间:2024/9/20 21:16:05