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.
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.
| 3-regular Klein graph | |
|---|---|
 | |
| Named after | Felix Klein |
| Vertices | 56 |
| Edges | 84 |
| Radius | 6 |
| Diameter | 6 |
| Girth | 7 |
| Automorphisms | 336 |
| Chromatic number | 3 |
| Chromatic index | 3 |
| Book thickness | 3 |
| Queue number | 2 |
| Properties | Symmetric Cubic Hamiltonian |
| Table of graphs and parameters | |
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. [1]
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. [2]
It can be derived from the 28-vertex Coxeter graph. [3]
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
 |  |
| 7-regular Klein graph | |
|---|---|
 | |
| Named after | Felix Klein |
| Vertices | 24 |
| Edges | 84 |
| Radius | 3 |
| Diameter | 3 |
| Girth | 3 |
| Automorphisms | 336 |
| Chromatic number | 4 |
| Chromatic index | 7 |
| Properties | Symmetric Hamiltonian |
| Table of graphs and parameters | |
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. [4]
It is the unique distance-regular graph with intersection array ; however, it is not a distance-transitive graph. [5]
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 . [6]
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.
In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.
In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphism
In the mathematical field of graph theory, the Gray graph is an undirected bipartite graph with 54 vertices and 81 edges. It is a cubic graph: every vertex touches exactly three edges. It was discovered by Marion C. Gray in 1932 (unpublished), then discovered independently by Bouwer 1968 in reply to a question posed by Jon Folkman 1967. The Gray graph is interesting as the first known example of a cubic graph having the algebraic property of being edge but not vertex transitive.
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.
In the mathematical field of graph theory, the Pappus graph is a bipartite, 3-regular, undirected graph with 18 vertices and 27 edges, formed as the Levi graph of the Pappus configuration. It is named after Pappus of Alexandria, an ancient Greek mathematician who is believed to have discovered the "hexagon theorem" describing the Pappus configuration. All the cubic, distance-regular graphs are known; the Pappus graph is one of the 13 such graphs.
In the mathematical field of graph theory, the Foster graph is a bipartite 3-regular graph with 90 vertices and 135 edges.
In the mathematical field of graph theory, the Möbius–Kantor graph is a symmetric bipartite cubic graph with 16 vertices and 24 edges named after August Ferdinand Möbius and Seligmann Kantor. It can be defined as the generalized Petersen graph G(8,3): that is, it is formed by the vertices of an octagon, connected to the vertices of an eight-point star in which each point of the star is connected to the points three steps away from it.
In the mathematical field of graph theory, the Shrikhande graph is a graph discovered by S. S. Shrikhande in 1959. It is a strongly regular graph with 16 vertices and 48 edges, with each vertex having degree 6. Every pair of nodes has exactly two other neighbors in common, whether or not the pair of nodes is connected.
In mathematics, a regular map is a symmetric tessellation of a closed surface. More precisely, a regular map is a decomposition of a two-dimensional manifold into topological disks such that every flag can be transformed into any other flag by a symmetry of the decomposition. Regular maps are, in a sense, topological generalizations of Platonic solids. The theory of maps and their classification is related to the theory of Riemann surfaces, hyperbolic geometry, and Galois theory. Regular maps are classified according to either: the genus and orientability of the supporting surface, the underlying graph, or the automorphism group.
In the mathematical field of graph theory, the Franklin graph is a 3-regular graph with 12 vertices and 18 edges.
In the mathematical field of graph theory, the Folkman graph is a 4-regular graph with 20 vertices and 40 edges. It is a regular bipartite graph with symmetries taking every edge to every other edge, but the two sides of its bipartition are not symmetric with each other, making it the smallest possible semi-symmetric graph. It is named after Jon Folkman, who constructed it for this property in 1967.
In the mathematical field of graph theory, the Biggs–Smith graph is a 3-regular graph with 102 vertices and 153 edges.
In the mathematical field of graph theory, the Dyck graph is a 3-regular graph with 32 vertices and 48 edges, named after Walther von Dyck.
In the mathematical field of graph theory, the Nauru graph is a symmetric, bipartite, cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru.
In the mathematical field of graph theory, the F26A graph is a symmetric bipartite cubic graph with 26 vertices and 39 edges.
In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges, rediscovered in 2002 and named after Ljubljana.
In the mathematical field of graph theory, the Tutte 12-cage or Benson graph is a 3-regular graph with 126 vertices and 189 edges. It is named after W. T. Tutte.
Italo Jose Dejter is an Argentine-born American mathematician, a retired professor of mathematics and computer science from the University of Puerto Rico, and a researcher in algebraic topology, differential topology, graph theory, coding theory and combinatorial designs. He obtained a Licentiate degree in mathematics from University of Buenos Aires in 1967, arrived at Rutgers University in 1970 by means of a Guggenheim Fellowship and obtained a Ph.D. degree in mathematics in 1975 under the supervision of Professor Ted Petrie, with support of the National Science Foundation. He was a professor at the Federal University of Santa Catarina, Brazil, from 1977 to 1984, with grants from the National Council for Scientific and Technological Development, (CNPq).
The 110-vertex Iofinova–Ivanov graph is, in graph theory, a semi-symmetric cubic graph with 110 vertices and 165 edges.
