Klein Graphs on:
[Wikipedia]
[Google]
[Amazon]
In the
In the mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, the Klein graphs are two different but related regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree o ...
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 ...
of genus
Genus ( plural genera ) is a taxonomic rank used in the biological classification of extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In the hierarchy of biological classification, genus com ...
3, in which they form dual graph
In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loop ...
s.
The cubic Klein graph
This is a 3- regular ( cubic) graph with 56 vertices and 84 edges, named afterFelix Klein
Christian Felix Klein (; 25 April 1849 – 22 June 1925) was a German mathematician and mathematics educator, known for his work with group theory, complex analysis, non-Euclidean geometry, and on the associations between geometry and group ...
.
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
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
3, chromatic index
In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...
3, radius 6, diameter 6 and girth
Girth may refer to:
;Mathematics
* Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space
* Girth (geometry), the perimeter of a parallel projection of a shape
* Girth ...
7. It is also a 3- vertex-connected and a 3- edge-connected graph. It has book thickness
In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie o ...
3 and queue number
In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings.
Defin ...
2.
It can be embedded in the genus
Genus ( plural genera ) is a taxonomic rank used in the biological classification of extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In the hierarchy of biological classification, genus com ...
-3 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 ...
(which can be represented as the Klein quartic
In hyperbolic geometry, the Klein quartic, named after Felix Klein, is a compact Riemann surface of genus with the highest possible order automorphism group for this genus, namely order orientation-preserving automorphisms, and automorphisms ...
), 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 regular polytopes and tessellations.
The Schläfli symbol is named after the 19th-century Swiss mathematician Ludwig Schläfli, who generalized Euclidean geometry to more ...
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.
It can be derived from the 28-vertex Coxeter graph
In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 known cubic distance-regular graphs. It is named after Harold Scott MacDonald Coxeter.
Properties
The Coxeter ...
.
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 asymmetric graph
In the mathematical field of graph theory, a graph is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices and of , there is an automorphism
:f : V(G) \rightarrow V(G)
such that
:f(u_1) = u_2 and f(v_1) = v_2.
In oth ...
.
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 chara ...
of this 56-vertex Klein graph is equal to
The 7-regular Klein graph
This is a 7- regular graph with 24 vertices and 84 edges, named afterFelix Klein
Christian Felix Klein (; 25 April 1849 – 22 June 1925) was a German mathematician and mathematics educator, known for his work with group theory, complex analysis, non-Euclidean geometry, and on the associations between geometry and group ...
.
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
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
4, chromatic index
In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...
7, radius 3, diameter 3 and girth
Girth may refer to:
;Mathematics
* Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space
* Girth (geometry), the perimeter of a parallel projection of a shape
* 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
In geometry, the Schläfli symbol is a notation of the form \ that defines regular polytopes and tessellations.
The Schläfli symbol is named after the 19th-century Swiss mathematician Ludwig Schläfli, who generalized Euclidean geometry to more ...
8.
It is the unique distance-regular graph
In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and .
...
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 carrie ...
.
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. Thecharacteristic 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 chara ...
of this 24-vertices Klein graph is equal to .
References
{{reflist Individual graphs Regular graphs