Möbius–Kantor graph
From Wikipedia, the free encyclopedia
| 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 |
In graph theory, the Möbius–Kantor graph is a symmetric bipartite cubic graph with 16 vertices and 24 edges. 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.
Contents |
[edit] Möbius–Kantor configuration
Möbius (1828) asked whether there exists a pair of polygons with p sides each, having the property that the vertices of one polygon lie on the lines through the edges of the other polygon, and vice versa. If so, the vertices and edges of these polygons would form a projective configuration. For p = 4 there is no solution in the Euclidean plane, but Kantor (1882) found pairs of polygons of this type, for a generalization of the problem in which the points and edges belong to the complex projective plane. That is, in Kantor's solution, the coordinates of the polygon vertices are complex numbers. Kantor's solution for p = 4, a pair of mutually-inscribed quadrilaterals in the complex projective plane, is called 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,ω2,1), (1,ω,0), (0,1,0), (0,−1,1),
where ω denotes the complex cube root of 1.
More abstractly, the Möbius–Kantor configuration can be described as a system of eight points and eight triples of points such that each point belongs to exactly three of the triples. Any two systems of this type are equivalent under some permutation of the points; that is, the Möbius–Kantor configuration is the unique projective configuration of type (8383). The Möbius–Kantor graph derives its name from being the Levi graph of the Möbius–Kantor configuration. It has one vertex per point and one vertex per triple, with an edge connecting two vertices if they correspond to a point and to a triple that contains that point.
The solution to Möbius' problem of mutually inscribed polygons for values of p greater than four is also of interest. In particular, one possible solution for p = 5 is the Desargues configuration, a set of ten points and ten lines, three points per line and three lines per point, that does admit a Euclidean realization.
[edit] Relation to hypercube
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, the Möbius–Kantor graph can also be drawn in the plane with all edges unit length, although such a drawing will necessarily have some pairs of crossing edges.
[edit] Topology and symmetry
The Möbius–Kantor graph cannot be embedded without crossings in the plane; it has crossing number 4, and is the smallest cubic graph with that crossing number (sequence A110507 in OEIS). However, it has an embedding in the torus in which all faces are hexagons (Marušič & Pisanski 2000).
There is an even more symmetric embedding of Möbius–Kantor graph in the double torus, with six octagonal faces, in which all 96 symmetries of the graph can be realized as symmetries 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.
The Möbius–Kantor graph is a symmetric graph, meaning that it has symmetries taking any vertex to any other vertex and any edge to any other edge. It is one of only seven symmetric generalized Petersen graphs (Frucht, Graver & Watkins 1971), and its symmetric double torus embedding is correspondingly one of only seven regular cubic maps in which the total number of vertices is twice the number of vertices per face (McMullen 1992). The Möbius–Kantor graph is the unique cubic symmetric graph with 16 vertices.
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.
[edit] 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
- Frucht, R.; Graver, J. E. & Watkins, M. E. (1971), “The groups of the generalized Petersen graphs”, Proceedings of the Cambridge Philosophical Society 70: 211–218.
- 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 Kaiserlichen Akademie der Wissenschaften, Wien 84 (1): 915–932.
- 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.
- Marušič, Dragan & Pisanski, Tomaž (2000), “The remarkable generalized Petersen graph G(8,3)”, Math. Slovaca 50: 117–121, <http://www.ijp.si/ftp/pub/Preprints/ps/97/pp572.ps>.
- McMullen, Peter (1992), “The regular polyhedra of type {p, 3} with 2p vertices”, Geometriae Dedicata 43 (3): 285–289, DOI 10.1007/BF00151518.
- Möbius, A. F. (1828), “Kann von zwei dreiseitigen Pyramiden einejede in Bezug auf die andere um- und eingeschriehen zugleich heissen?”, J. Reine Angew. Math. 3: 273–278. 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.
