# MĂ¶biusâKantor graph Information

https://en.wikipedia.org/wiki/MĂ¶biusâKantor_graph
MĂ¶biusâKantor graph Named after August Ferdinand MĂ¶bius and S. Kantor
Vertices16
Edges24
Diameter4
Girth6
Automorphisms96
Chromatic number2
Chromatic index3
Genus1
Book thickness3
Queue number2
Properties Symmetric
Hamiltonian
Bipartite
Cubic
Unit distance
Cayley graph
Perfect
Orientably simple
Table of graphs and parameters

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.

## 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. 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 configuration may also be described algebraically in terms of the abelian group $\mathbb {Z} _{3}\times \mathbb {Z} _{3}$ with nine elements. This group has four subgroups of order three (the subsets of elements of the form $(i,0)$ , $(i,i)$ , $(i,2i)$ , and $(0,i)$ respectively), each of which can be used to partition the nine group elements into three cosets of three elements per coset. These nine elements and twelve cosets form a configuration, the Hesse configuration. Removing the zero element and the four cosets containing zero gives rise to the MĂ¶biusâKantor configuration.

## As a subgraph

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.

The MĂ¶biusâKantor graph also occurs many times as in induced subgraph of the HoffmanâSingleton graph. Each of these instances is in fact an eigenvector of the Hoffman-Singleton graph, with associated eigenvalue -3. Each vertex not in the induced MĂ¶biusâKantor graph is adjacent to exactly four vertices in the MĂ¶biusâKantor graph, two each in half of a bipartition of the MĂ¶biusâKantor graph.

## Topology The MĂ¶biusâKantor graph, embedded on the torus. Edges extending upwards from the central square should be viewed as connecting with the corresponding edge extending downwards from the square, and edges extending leftwards from the square should be viewed as connecting with the corresponding edge extending rightwards.

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 in the OEIS). Additionally, it provides an example of a graph all of whose subgraphs' crossing numbers differ from it by two or more.  However, it is a toroidal graph: it has an embedding in the torus in which all faces are hexagons ( MaruĆĄiÄ & Pisanski 2000). The dual graph of this embedding is the hyperoctahedral graph K2,2,2,2.

There is an even more symmetric embedding of MĂ¶biusâKantor graph in the double torus which is a regular map, 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. The Cayley graph on 96 vertices is a flag graph of the genus 2 regular map having MĂ¶biusâKantor graph as a skeleton. This means it can be obtained from the regular map as a skeleton of the dual of its barycentric subdivision. 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. In 2013 a rotating version of the sculpture was unveiled at Colgate University.

The MĂ¶biusâKantor graph admits an embedding into a triple torus (genus 3 torus) that is a regular map having four 12-gonal faces, and is the Petrie dual of the double torus embedding described above; ( MaruĆĄiÄ & Pisanski 2000).

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.

## Algebraic properties

The automorphism group of the MĂ¶biusâKantor graph is a group of order 96.  It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore the MĂ¶biusâKantor graph is a symmetric graph. It has automorphisms that take any vertex to any other vertex and any edge to any other edge. According to the Foster census, the MĂ¶biusâKantor graph is the unique cubic symmetric graph with 16 vertices, and the smallest cubic symmetric graph which is not also distance-transitive.  The MĂ¶biusâKantor graph is also a Cayley graph.

The generalized Petersen graph G(n,k) is vertex-transitive if and only if n = 10 and k =2 or if k2 âĄ Â±1 (mod n) and is edge-transitive only in the following seven cases: (n,k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), or (24,5) ( Frucht, Graver & Watkins 1971). So the MĂ¶biusâKantor graph is one of only seven symmetric Generalized Petersen graphs. 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). Among the seven symmetric generalized Petersen graphs are the cubical graph $G(4,1)$ , the Petersen graph $G(5,2)$ , the dodecahedral graph $G(10,2)$ , the Desargues graph $G(10,3)$ and the Nauru graph $G(12,5)$ .

The characteristic polynomial of the MĂ¶biusâKantor graph is equal to

$(x-3)(x-1)^{3}(x+1)^{3}(x+3)(x^{2}-3)^{4}.\$ 