In the

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

field of

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, the Klein graphs are two different but related

regular graph In graph theory, a regular graph is a Graph (discrete mathematics), graph where each Vertex (graph theory), vertex has the same number of neighbors; i.e. every vertex has the same Degree (graph theory), degree or valency. A regular directed graph ...

s, each with 84 edges. Each can be embedded in the orientable

surface A surface, as the term is most generally used, is the outermost or uppermost layer of a physical object or space. It is the portion or region of the object that can first be perceived by an observer using the senses of sight and touch, and is ...

genus Genus (; : genera ) is a taxonomic rank above species and below family (taxonomy), family as used in the biological classification of extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In bino ...

3, in which they form

dual graph In the mathematics, mathematical discipline of graph theory, the dual graph of a planar graph is a graph that has a vertex (graph theory), vertex for each face (graph theory), face of . The dual graph has an edge (graph theory), edge for each p ...

The cubic Klein graph

This is a 3- regular (

cubic Cubic may refer to: Science and mathematics * Cube (algebra), "cubic" measurement * Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex ** Cubic crystal system, a crystal system w ...

) graph with 56 vertices and 84 edges, named after

Felix Klein Felix Christian Klein (; ; 25 April 1849 – 22 June 1925) was a German mathematician and Mathematics education, mathematics educator, known for his work in group theory, complex analysis, non-Euclidean geometry, and the associations betwe ...

. It is

Hamiltonian Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system ** Dyall Hamiltonian, a modified 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

-3 orientable

(which can be represented as the Klein quartic), where it forms the Klein map with 24 heptagonal faces,

Schläfli symbol In geometry, the Schläfli symbol is a notation of the form \ that defines List of regular polytopes and compounds, regular polytopes and tessellations. The Schläfli symbol is named after the 19th-century Swiss mathematician Ludwig Schläfli, wh ...

₈. According to the ''Foster census'', the Klein graph, referenced as F056B, is the only cubic symmetric graph on 56 vertices which is not bipartite. It can be derived from the 28-vertex Coxeter graph.

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 In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The ...

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

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

. It is

, 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,

₈. It is the unique distance-regular graph with intersection array

\

; however, it is not a

distance-transitive graph In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices and at any distance , and any other two vertices and at the same distance, there is an automorphism of the graph that carri ...

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

of this 24-vertices Klein graph is equal to

(x-7) (x+1)^7 (x^2-7)^8

References

{{reflist Individual graphs Regular graphs