Möbius–Kantor graph
| Möbius–Kantor graph | |
|---|---|
 | |
| Named after | August Ferdinand Möbius and S. Kantor |
| Vertices | 16 |
| Edges | 24 |
| Girth | 6 |
| Chromatic number | 2 |
| Chromatic index | 3 |
| Table of graphs and parameters | |
In graph theory, the Möbius–Kantor graph is the generalized Petersen graph G(8,3), a symmetric bipartite cubic graph with 16 vertices and 24 edges.
Basic properties
The Möbius–Kantor graph is a subgraph of the four-dimensional hypercube graph, formed by removing eight edges from the hypercube (Coxeter 1950). Since the hypercube is a unit distance graph, so is the Möbius–Kantor graph.
Möbius–Kantor configuration
The Möbius–Kantor graph derives its name from being the Levi graph of the Möbius–Kantor configuration. This is the unique projective configuration of type (8383), a system of eight points and eight triples of points such that each point belongs to exactly three of the triples.
Möbius (1828) had asked whether there exists a pair of p-gons, the vertices of each of which lie on the edges of the other. Kantor (1882) provided a positive solution, if one generalizes a polygon to allow its points and lines to have complex number coordinates; his solution for p = 4 is the Möbius–Kantor configuration.
Coxeter (1950) supplies the following simple complex projective coordinates for the eight points of the Möbius–Kantor configuration:
- (1,0,0), (0,0,1), (ω, -1, 1), (-1, 0, 1),
- (-1,&omega2,1), (1,ω,0), (0,1,0), (0,-1,1),
where ω denotes the complex cube root of 1.
The Möbius–Kantor configuration cannot be realized as a set of points and straight lines in the plane.
Topology and symmetry
The Möbius–Kantor graph cannot be embedded in the plane, but it has a vertex-transitive embedding in the torus, in which all faces are hexagons.
There is an even more symmetric embedding of Möbius–Kantor graph in the double torus, with six octagonal faces, in which all 96 automorphisms of the graph can be realized as automorphisms of the embedding; Coxeter (1950) credits this embedding to Threlfall (1932). Its 96-element symmetry group has a Cayley graph that can itself be embedded on the double torus, and was shown by Tucker (1984) to be the unique group with genus two. A sculpture by DeWitt Godfrey and Duane Martinez showing the double torus embedding of the symmetries of the Möbius–Kantor graph was unveiled at the Technical Museum of Slovenia as part of the 6th Slovenian International Conference on Graph Theory in 2007.
Lijnen & Ceulemans (2004), motivated by an investigation of potential chemical structures of carbon compounds, studied the family of all embeddings of the Möbius–Kantor graph onto 2-manifolds; they showed that there are 759 inequivalent embeddings.
The Möbius–Kantor graph is the unique cubic symmetric graph with 16 vertices.
References
- Coxeter, H. S. M. (1950), "Self-dual configurations and regular graphs", Bulletin of the American Mathematical Society, 56: 413–455, doi:10.1090/S0002-9904-1950-09407-5
- Kantor, S. (1882), "Über die Configurationen (3, 3) mit den Indices 8, 9 und ihren
Zusammenhang mit den Curven dritter Ordnung", Sitzungsberichte der Mathematisch- Naturwissenschaftliche Classe der K. Akademie der Wissenschaften, Wien, 84 (1): 915–932 {{citation}}: line feed character in |journal= at position 36 (help); line feed character in |title= at position 64 (help).
- Lijnen, E.; Ceulemans, A. (2004), "Oriented 2-Cell Embeddings of a Graph and Their Symmetry Classification: Generating Algorithms and Case Study of the Möbius-Kantor Graph", J. Chem. Inf. Comput. Sci., 44 (5): 1552–1564, doi:10.1021/ci049865c S0095-2338(04)09865-8
{{citation}}: Check|doi=value (help).
- Marušič, Dragan; Pisanski, Tomaž (2000), "The remarkable generalized Petersen graph G(8,3)", Math. Slovaca, 50: 117–121.
- Möbius, A. F. (1828), Kann von zwei dreiseitigen Pyramiden einejede in Bezug auf die andere um- und eingeschriehen zugleich heissen?
{{citation}}: line feed character in|title=at position 64 (help). In Gesammelte Werke (1886), vol. 1, pp. 439–446.
- Tucker, Thomas W. (1984), "There is only one group of genus two", Journal of Combinatorial Theory, Series B, 36: 269–275.
- Threlfall, W. (1932), "Gruppenbilder", Abhandlungen der Mathematisch-Physischen Klasse der Sâchsischen Akademie der Wissenschaften, 41 (6): 1–59.