The term Klein graph is used in the mathematical field of graph theory for two different but related regular graphs, each with 84 edges. Both can be embedded in the orientable surface of genus 3, in which they are dual graphs.

The cubic Klein graph

edit
Klein graph
 
The (cubic) Klein graph
Named afterFelix Klein
Vertices56
Edges84
Radius6
Diameter6
Girth7
Automorphisms336
Chromatic number3
Chromatic index3
PropertiesSymmetric
Cubic
Hamiltonian
Cayley graph
Table of graphs and parameters

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

It is a Hamiltonian. It has chromatic number 4, chromatic index 3, radius 6, diameter 6 and girth 7. It is also a 3-vertex-connected and a 3-edge-connected graph.

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.[1]

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

Algebraic properties

edit

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.

edit

The 7-valent Klein graph

edit
Klein graph
Named afterFelix Klein
Vertices24
Edges84
Radius3
Diameter3
Girth3
Automorphisms336
Chromatic number3
PropertiesSymmetric
Hamiltonian
Table of graphs and parameters

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

It is a Hamiltonian. It has chromatic number 3, chromatic index 3, 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.[3]

Algebraic properties

edit

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 the Klein graph is equal to  .[4]

References

edit
  1. ^ Conder, M.; Dobcsányi, P. (2002), "Trivalent symmetric graphs up to 768 vertices", J. Combin. Math. Combin. Comput., 40: 41–63.
  2. ^ Dejter, Italo. "From the Coxeter graph to the Klein graph". CiteSeer. CiteSeerX 10.1.1.188.2580. Retrieved 23 March 2013.
  3. ^ "A Polyhedral Realization of Felix Klein's Map {3, 7}8 on a Riemann Surface of Genus 3". J. London Math. Soc. s2-32 (3). 1985. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
  4. ^ Weisstein, Eric. "Klein graph". MathWorld. Wolfram Research. Retrieved 23 March 2013.

Category:Individual graphs Category:Regular graphs