Klein graphs

The cubic Klein graph

Cubic Hamiltonian

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

It is Hamiltonian, 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.

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.{{cite journal

It can be derived from the 28-vertex Coxeter graph.{{cite journal

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-vertex Klein graph is equal to x^7 ,(x-3),(x+2)^6 \left(x^2-2\right)^6 \left(x^2+x-4\right)^7 \left(x^2-2 x-1\right)^8

The 7-regular Klein graph {{anchor|The 7-valent Klein graph}}

Hamiltonian

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

It is Hamiltonian, 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.{{cite journal

It is the unique distance-regular graph with intersection array {7,4,1; 1,2,7}; however, it is not a distance-transitive graph.

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 (x-7) (x+1)^7 (x^2-7)^8.

References

References

1. Wolz, Jessica; ''Engineering Linear Layouts with SAT.'' Master Thesis, University of Tübingen, 2018
2. (1989). "Distance-Regular Graphs". [[Springer-Verlag]].
3. (2006). "Characterizing distance-regularity of graphs by the spectrum". [[Journal of Combinatorial Theory.