Möbius–Kantor graph

<h2 id="mbiuskantor-configuration">Möbius–Kantor configuration</h2>
Main article: <a href="/facts/M%25C3%25B6bius%25E2%2580%2593Kantor_configuration/NgQIafId">Möbius–Kantor configuration</a>

Möbius (1828) asked whether there exists a pair of <a href="/facts/Polygon/yAq7RjPz">polygons</a> 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 <a href="/facts/Projective_configuration/2EJN52Ud">projective configuration</a>. For p = 4 there is no solution in the <a href="/facts/Euclidean_plane/tAUtRFcn">Euclidean plane</a>, 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 <a href="/facts/Complex_projective_plane/5WFpDyeV">complex projective plane</a>. That is, in Kantor's solution, the coordinates of the polygon vertices are <a href="/facts/Complex_number/2w7mqI7e">complex numbers</a>. 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 <a href="/facts/Levi_graph/pMnp7zkv">Levi graph</a> 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 <a href="/facts/Abelian_group/FfWwmx4R">abelian group</a> 
 
 
 
 
 
 Z
 
 
 3
 
 
 ×
 
 
 Z
 
 
 3
 
 
 
 
 {\displaystyle \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
 )
 
 
 {\displaystyle (i,0)}
 
, 
 
 
 
 (
 i
 ,
 i
 )
 
 
 {\displaystyle (i,i)}
 
, 
 
 
 
 (
 i
 ,
 2
 i
 )
 
 
 {\displaystyle (i,2i)}
 
, and 
 
 
 
 (
 0
 ,
 i
 )
 
 
 {\displaystyle (0,i)}
 
), each of which can be used to partition the nine group elements into three <a href="/facts/Coset/zFgQUTLY">cosets</a> of three elements per coset. These nine elements and twelve cosets form a configuration, the <a href="/facts/Hesse_configuration/RL5fHwPJ">Hesse configuration</a>. Removing the zero element and the four cosets containing zero gives rise to the Möbius–Kantor configuration.

<h2 id="as-a-subgraph">As a subgraph</h2>
The Möbius–Kantor graph is a <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">subgraph</a> of the four-dimensional <a href="/facts/Hypercube_graph/pwfGEl9J">hypercube graph</a>, formed by removing eight edges from the hypercube.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> Since the hypercube is a <a href="/facts/Unit_distance_graph/8y4Ctq53">unit distance graph</a>, 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 an induced subgraph of the <a href="/facts/Hoffman%25E2%2580%2593Singleton_graph/fqSQJhGw">Hoffman–Singleton graph</a>. Each of these instances is in fact an <a href="/facts/Spectral_graph_theory/tBttgGTh">eigenvector</a> 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 <a href="/facts/Bipartite_graph/xWcXV9MB">bipartition</a> of the Möbius–Kantor graph.

<h2 id="topology">Topology</h2>

The Möbius–Kantor graph cannot be embedded without crossings in the plane; it has <a href="/facts/Crossing_number_(graph_theory)/x3Yz6UhF">crossing number</a> 4, and is the smallest cubic graph with that crossing number.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> Additionally, it provides an example of a graph all of whose subgraphs' crossing numbers differ from it by two or more.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
However, it is a <a href="/facts/Toroidal_graph/jtgbddDj">toroidal graph</a>: it has an embedding in the <a href="/facts/Torus/J9SkaV1W">torus</a> in which all faces are <a href="/facts/Hexagon/DPzuCzWE">hexagons</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> The <a href="/facts/Dual_graph/1t14hhEF">dual graph</a> of this embedding is the <a href="/facts/Tur%25C3%25A1n_graph/y0hzJqQQ">hyperoctahedral graph</a> K2,2,2,2.
There is an even more symmetric embedding of Möbius–Kantor graph in the <a href="/facts/Double_torus/VLaXReyP">double torus</a> which is a <a href="/facts/Regular_map_(graph_theory)/4ahwy17x">regular map</a>, with six <a href="/facts/Octagon/H5PuP3wP">octagonal</a> faces, in which all 96 symmetries of the graph can be realized as symmetries of the embedding<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> Its 96-element <a href="/facts/Symmetry_group/CNqeseMp">symmetry group</a> has a <a href="/facts/Cayley_graph/QxoxNnys">Cayley graph</a> that can itself be embedded on the double torus, and was shown by Tucker (1984) to be the unique group with <a href="/facts/Genus_(mathematics)/o1Yhf8ty">genus</a> 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 <a href="/facts/DeWitt_Godfrey/TsgogzSp">DeWitt Godfrey</a> and Duane Martinez showing the double torus embedding of the symmetries of the Möbius–Kantor graph was unveiled at the Technical Museum of <a href="/facts/Slovenia/EcYU22W4">Slovenia</a> as part of the 6th Slovenian International Conference on Graph Theory in 2007. In 2013 a rotating version of the sculpture was unveiled at <a href="/facts/Colgate_University/lmUsfsby">Colgate University</a>.
The Möbius–Kantor graph admits an embedding into a <a href="/facts/Triple_torus/VLaXReyP">triple torus</a> (genus 3 torus) that is a <a href="/facts/Regular_map_(graph_theory)/4ahwy17x">regular map</a> having four 12-gonal faces, and is the <a href="/facts/Petrie_dual/oyk4jEHM">Petrie dual</a> of the double torus embedding described above.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
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-<a href="/facts/Manifold/rXPERJtu">manifolds</a>; they showed that there are 759 inequivalent embeddings. The genus 1 embedding, which is not a regular map, is seen in the diagram above.

<h2 id="algebraic-properties">Algebraic properties</h2>
The automorphism group of the Möbius–Kantor graph is a group of order 96.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore, the Möbius–Kantor graph is a <a href="/facts/Symmetric_graph/vPVWrnjb">symmetric graph</a>. 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 <a href="/facts/Distance-transitive_graph/HgH4heaB">distance-transitive</a>.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> The Möbius–Kantor graph is also a <a href="/facts/Cayley_graph/QxoxNnys">Cayley graph</a>.
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).<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> 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.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> Among the seven symmetric generalized Petersen graphs are the <a href="/facts/Cube/65lUaAqN">cubical graph</a> 
 
 
 
 G
 (
 4
 ,
 1
 )
 
 
 {\displaystyle G(4,1)}
 
, the <a href="/facts/Petersen_graph/lLRxXpQs">Petersen graph</a> 
 
 
 
 G
 (
 5
 ,
 2
 )
 
 
 {\displaystyle G(5,2)}
 
, the <a href="/facts/Dodecahedron/7r519eCl">dodecahedral graph</a> 
 
 
 
 G
 (
 10
 ,
 2
 )
 
 
 {\displaystyle G(10,2)}
 
, the <a href="/facts/Desargues_graph/M6sXWfFK">Desargues graph</a> 
 
 
 
 G
 (
 10
 ,
 3
 )
 
 
 {\displaystyle G(10,3)}
 
 and the <a href="/facts/Nauru_graph/n9Mgs9Kx">Nauru graph</a> 
 
 
 
 G
 (
 12
 ,
 5
 )
 
 
 {\displaystyle G(12,5)}
 
.
The <a href="/facts/Characteristic_polynomial/7m8roDqo">characteristic polynomial</a> of the Möbius–Kantor graph is equal to<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>

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

The Möbius–Kantor graph is a double cover of the graph of the cube.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Pauli_group/ssEYujzc">Pauli group</a>, whose <a href="/facts/Cayley_graph/QxoxNnys">Cayley graph</a> is the Möbius–Kantor graph</li></ul>
<h2 id="notes">Notes</h2>

<ul><li><a href="/facts/Marston_Conder/tC7nJDGt">Conder, Marston</a>; Dobcsányi, Peter (2002), "Trivalent symmetric graphs on up to 768 vertices", Journal of Combinatorial Mathematics and Combinatorial Computing, 40: 41–63, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1887966">1887966</a>.</li>
<li><a href="/facts/Harold_Scott_MacDonald_Coxeter/D2l5jWGG">Coxeter, H. S. M.</a> (1950), "Self-dual configurations and regular graphs", <a href="/facts/Bulletin_of_the_American_Mathematical_Society/8ER5KY5z">Bulletin of the American Mathematical Society</a>, 56 (5): 413–455, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1090%2FS0002-9904-1950-09407-5">10.1090/S0002-9904-1950-09407-5</a>.</li>
<li><a href="/facts/Robert_Frucht/euMmDpxn">Frucht, Robert</a>; Graver, Jack E.; Watkins, Mark E. (1971), "The groups of the generalized Petersen graphs", <a href="/facts/Mathematical_Proceedings_of_the_Cambridge_Philosophical_Society/KUUzcS7S">Mathematical Proceedings of the Cambridge Philosophical Society</a>, 70 (2): 211–218, <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1971PCPS...70..211F">1971PCPS...70..211F</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1017%2FS0305004100049811">10.1017/S0305004100049811</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0289365">0289365</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:122686848">122686848</a>.</li>
<li><a href="/facts/Seligmann_Kantor/mB5QhuyJ">Kantor, Seligmann</a> (1882), "Über die Configurationen (3, 3) mit den Indices 8, 9 und ihren Zusammenhang mit den Curven dritter Ordnung", Sitzungsberichte der Mathematisch-Naturwissenschaftlichen Classe der Kaiserlichen Akademie der Wissenschaften, Wien, 84 (1): 915–932.</li>
<li>Lijnen, Erwin; Ceulemans, Arnout (2004), "Oriented 2-Cell Embeddings of a Graph and Their Symmetry Classification: Generating Algorithms and Case Study of the Möbius-Kantor Graph", <a href="/facts/Journal_of_Chemical_Information_and_Modeling/QUD3AUmL">Journal of Chemical Information and Modeling</a>, 44 (5): 1552–1564, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1021%2Fci049865c">10.1021/ci049865c</a>, <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/15446812">15446812</a>.</li>
<li><a href="/facts/Dragan_Maru%25C5%25A1i%25C4%258D/lFAvpMCS">Marušič, Dragan</a>; <a href="/facts/Toma%25C5%25BE_Pisanski/cVNoaUGH">Pisanski, Tomaž</a> (2000), <a href="http://dml.cz/dmlcz/133137">"The remarkable generalized Petersen graph G(8,3)"</a>, Mathematica Slovaca, 50: 117–121.</li>
<li><a href="/facts/Peter_McMullen/E0HuIJJh">McMullen, Peter</a> (1992), "The regular polyhedra of type 
 
 
 
 {
 p
 ,
 3
 }
 
 
 {\displaystyle \{p,3\}}
 
 with 
 
 
 
 2
 p
 
 
 {\displaystyle 2p}
 
 vertices", <a href="/facts/Geometriae_Dedicata/8sNcnkJs">Geometriae Dedicata</a>, 43 (3): 285–289, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF00151518">10.1007/BF00151518</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:119591683">119591683</a>.</li>
<li>McQuillan, Dan; Richter, R. Bruce (1992), "On the crossing numbers of certain generalized Petersen graphs", <a href="/facts/Discrete_Mathematics_(journal)/K4e6z8wQ">Discrete Mathematics</a>, 104 (3): 311–320, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0012-365X%2892%2990453-M">10.1016/0012-365X(92)90453-M</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1171327">1171327</a>.</li>
<li><a href="/facts/August_Ferdinand_M%25C3%25B6bius/8ryQFhWv">Möbius, August Ferdinand</a> (1828), <a href="https://zenodo.org/record/2522230">"Kann von zwei dreiseitigen Pyramiden eine jede in Bezug auf die andere um- und eingeschrieben zugleich heissen?"</a>, <a href="/facts/Crelle%2527s_Journal/YCcRSaAQ">Journal für die reine und angewandte Mathematik</a>, 3: 273–278; in Gesammelte Werke (1886), vol. 1, pp. 439–446.</li>
<li><a href="/facts/Thomas_W._Tucker/kg6wYbm1">Tucker, Thomas W.</a> (1984), "There is only one group of genus two", <a href="/facts/Journal_of_Combinatorial_Theory/oYS6G76K">Journal of Combinatorial Theory</a>, Series B, 36 (3): 269–275, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0095-8956%2884%2990032-7">10.1016/0095-8956(84)90032-7</a>.</li>
<li><a href="/facts/William_Threlfall/utLTgQzK">Threlfall, William</a> (1932), "Gruppenbilder", Abhandlungen der Mathematisch-Physischen Klasse der Sächsischen Akademie der Wissenschaften, 41 (6): 1–59.</li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a>, <a href="https://mathworld.wolfram.com/Moebius-KantorGraph.html">"Möbius-Kantor Graph"</a>, <a href="/facts/MathWorld/yc1jodbq">MathWorld</a></li>
<li><a href="https://www.youtube.com/watch?v=DLdwzyP6Cmk">Unveiling the Colgate University sculpture</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Coxeter 1950. - Coxeter, H. S. M. (1950), "Self-dual configurations and regular graphs", Bulletin of the American Mathematical Society, 56 (5): 413–455, doi:10.1090/S0002-9904-1950-09407-5 <a href="https://doi.org/10.1090%2FS0002-9904-1950-09407-5" target="_blank">https://doi.org/10.1090%2FS0002-9904-1950-09407-5</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">OEIS sequence A110507 <a href="https://oeis.org/A110507" target="_blank">https://oeis.org/A110507</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">McQuillan & Richter 1992. - McQuillan, Dan; Richter, R. Bruce (1992), "On the crossing numbers of certain generalized Petersen graphs", Discrete Mathematics, 104 (3): 311–320, doi:10.1016/0012-365X(92)90453-M, MR 1171327 <a href="https://doi.org/10.1016%2F0012-365X%2892%2990453-M" target="_blank">https://doi.org/10.1016%2F0012-365X%2892%2990453-M</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Marušič & Pisanski 2000. - Marušič, Dragan; Pisanski, Tomaž (2000), "The remarkable generalized Petersen graph G(8,3)", Mathematica Slovaca, 50: 117–121 <a href="http://dml.cz/dmlcz/133137" target="_blank">http://dml.cz/dmlcz/133137</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Coxeter (1950) credits this embedding to Threlfall (1932). - Coxeter, H. S. M. (1950), "Self-dual configurations and regular graphs", Bulletin of the American Mathematical Society, 56 (5): 413–455, doi:10.1090/S0002-9904-1950-09407-5 <a href="https://doi.org/10.1090%2FS0002-9904-1950-09407-5" target="_blank">https://doi.org/10.1090%2FS0002-9904-1950-09407-5</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Marušič & Pisanski 2000. - Marušič, Dragan; Pisanski, Tomaž (2000), "The remarkable generalized Petersen graph G(8,3)", Mathematica Slovaca, 50: 117–121 <a href="http://dml.cz/dmlcz/133137" target="_blank">http://dml.cz/dmlcz/133137</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Marušič & Pisanski 2000. - Marušič, Dragan; Pisanski, Tomaž (2000), "The remarkable generalized Petersen graph G(8,3)", Mathematica Slovaca, 50: 117–121 <a href="http://dml.cz/dmlcz/133137" target="_blank">http://dml.cz/dmlcz/133137</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Conder & Dobcsányi 2002. - Conder, Marston; Dobcsányi, Peter (2002), "Trivalent symmetric graphs on up to 768 vertices", Journal of Combinatorial Mathematics and Combinatorial Computing, 40: 41–63, MR 1887966 <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1887966" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=1887966</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Frucht, Graver & Watkins 1971. - Frucht, Robert; Graver, Jack E.; Watkins, Mark E. (1971), "The groups of the generalized Petersen graphs", Mathematical Proceedings of the Cambridge Philosophical Society, 70 (2): 211–218, Bibcode:1971PCPS...70..211F, doi:10.1017/S0305004100049811, MR 0289365, S2CID 122686848 <a href="https://ui.adsabs.harvard.edu/abs/1971PCPS...70..211F" target="_blank">https://ui.adsabs.harvard.edu/abs/1971PCPS...70..211F</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">McMullen 1992. - McMullen, Peter (1992), "The regular polyhedra of type 
 
 
 
 {
 p
 ,
 3
 }
 
 
 {\displaystyle \{p,3\}}
 
 with 
 
 
 
 2
 p
 
 
 {\displaystyle 2p}
 
 vertices", Geometriae Dedicata, 43 (3): 285–289, doi:10.1007/BF00151518, S2CID 119591683 <a href="https://doi.org/10.1007%2FBF00151518" target="_blank">https://doi.org/10.1007%2FBF00151518</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Brouwer, Andrew E. "Möbius-Kantor graph". www.win.tue.nl. Retrieved 2024-07-21. <a href="https://www.win.tue.nl/~aeb/drg/graphs/MoebiusKantor.html" target="_blank">https://www.win.tue.nl/~aeb/drg/graphs/MoebiusKantor.html</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Coxeter 1950. - Coxeter, H. S. M. (1950), "Self-dual configurations and regular graphs", Bulletin of the American Mathematical Society, 56 (5): 413–455, doi:10.1090/S0002-9904-1950-09407-5 <a href="https://doi.org/10.1090%2FS0002-9904-1950-09407-5" target="_blank">https://doi.org/10.1090%2FS0002-9904-1950-09407-5</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
</ol>

Möbius–Kantor graph open-in-new

Möbius–Kantor graph