Klein graphs

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

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

It is

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}₈.

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 PGL₂(7) of order 336, which has PSL₂(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 ${\displaystyle x^{7}\,(x-3)\,(x+2)^{6}\left(x^{2}-2\right)^{6}\left(x^{2}+x-4\right)^{7}\left(x^{2}-2x-1\right)^{8}}$

chromatic index is 3)

The 7-regular Klein graph

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

It is

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}₈.^[4]

It is the unique distance-regular graph with intersection array ${\displaystyle \{7,4,1;1,2,7\}}$; 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 ${\displaystyle (x-7)(x+1)^{7}(x^{2}-7)^{8}}$.^[6]

References