Möbiův graf - Cantor

Möbiův–Cantorův graf

Pojmenoval podle	August Ferdinand Möbius a Z. Kantor
Vrcholy	16
žebra	24
Poloměr	čtyři
Průměr	čtyři
obvod	6
Automorfismy	96
Chromatické číslo	2
Chromatický index	3
Rod	jeden
Vlastnosti	symetrický Hamiltonův bipartitní kubická jednotka vzdálenost Cayleyův graf dokonalý jednoduše orientovatelný

Möbius-Cantorův graf je symetrický bipartitní kubický graf s 16 vrcholy a 24 hranami, pojmenovaný po Augustu Ferdinandu Möbiovi a Seligmanu Cantorovi (1857–1903). To může být definováno jako zobecněný Petersenův graf , to znamená, že je tvořen vrcholy osmiúhelníku spojeného s osmiúhelníkovou hvězdou, ve které je každý bod připojen ke třetímu bodu v řadě. $G(8;3)$

Konfigurace Möbius-Cantor

Möbius v roce 1828 [1] nastolil otázku existence dvojice mnohoúhelníků se stranami v každém s tou vlastností, že vrcholy jednoho mnohoúhelníku leží na přímkách procházejících stranami druhého a naopak. Pokud takový pár existuje, pak vrcholy a strany těchto polygonů musí tvořit projektivní konfiguraci . Neboť v euklidovské rovině neexistuje žádné řešení , ale v roce 1882 Kantor [2] našel pár polygonů tohoto typu při zobecnění problému, ve kterém body a hrany patří do komplexní projektivní roviny , tedy v Cantorově řešení. , souřadnice vrcholů mnohoúhelníku jsou komplexní čísla . Cantorovo řešení pro dvojici vzájemně vepsaných čtyřúhelníků v komplexní projektivní rovině se nazývá Möbiova-Cantorova konfigurace . Möbius-Kantorův graf má svůj název podle Möbius-Cantorovy konfigurace, protože je to Leviho graf této konfigurace. Graf má jeden vrchol pro každý konfigurační bod a jeden bod pro každou trojici a hrany spojují dva vrcholy, pokud jeden vrchol odpovídá bodu a druhý trojici obsahující tento bod. $p$ $p=4$ $p=4$

Vztah s hyperkrychlí

Möbiův-Cantorův graf je podgrafem čtyřrozměrného grafu hyperkrychle a vzniká odstraněním osmi hran z hyperkrychle [3] . Vzhledem k tomu, že hyperkrychle je graf jednotkové vzdálenosti , Möbius-Cantorův graf lze také nakreslit v rovině se všemi stranami jednotkové délky, ačkoli takové znázornění by vedlo ke křížení hran.

Topologie

Möbiův-Cantorův graf nelze vložit do roviny bez průsečíků, jeho číslo křížení je 4 a je to nejmenší kubický graf s takovým počtem křížení [4] . Kromě toho je v grafu uveden příklad grafu, jehož všechny podgrafy mají počet průsečíků dva a více odlišný od počtu průsečíků samotného grafu [5] . Je však toroidní - je zde zapuštěno do torusu , ve kterém jsou všechny jeho plochy šestiúhelníky [6] . Duální graf tohoto vložení je hyperoktaedrový graf . $K_{2,2,2,2}$

Dochází k ještě symetričtějšímu vnoření Möbiova-Cantorova grafu do dvojitého torusu , což je pravidelná mapa a má šest osmihranných ploch, ve kterých lze všech 96 symetrií grafu realizovat jako symetrie vnoření [7] . 96prvková skupina symetrie vkládání má Cayleyův graf , který lze vložit do dvojitého torusu. V roce 1984 se ukázalo, že se jedná o jedinou skupinu rodu dva [8] .

Socha DeWitta Godfreyho a Duana Martineze ve formě dvojitého torusu s vloženým Möbius-Kantorovým grafem byla vystavena v Technickém muzeu Slovinska na 6. slovinské mezinárodní konferenci o teorii grafů v roce 2007. V roce 2013 byla na Colgate University vystavena rotující verze sochy .

Möbius-Cantorův graf připouští vložení do trojitého torusu (torus třetího druhu), který dává pravidelnou mapu se čtyřmi 12-gonálními plochami; [6] .

V roce 2004 byla v rámci studia možných chemických uhlíkových struktur studována rodina všech vnoření Möbiova-Cantorova grafu ve dvourozměrných varietách , v důsledku čehož se ukázalo, že existuje 759 neekvivalentních vložení [9]. .

Algebraické vlastnosti

Grupa automorfismu Möbiova-Cantorova grafu je grupa řádu 96 [10] . Působí tranzitivně na vrcholy a hrany, takže Möbiův-Cantorův graf je symetrický . Má automorfismy, které mapují jakýkoli vrchol na jakýkoli jiný a jakoukoli hranu na jakoukoli jinou. Podle Fosterova seznamu je Möbiův-Cantorův graf jediným symetrickým grafem s 16 vrcholy a nejmenším kubickým symetrickým grafem, který není tranzitivní na vzdálenost [11] . Möbius-Cantorův graf je také grafem Cayleyho .

Zobecněný Petersenův graf je vertex-tranzitivní tehdy a jen tehdy a , nebo když , a hranově tranzitivní pouze v následujících sedmi případech: [12] . Möbiův-Cantorův graf je tedy jedním z těchto sedmi hranově tranzitivních zobecněných Petersenových grafů. Jeho symetrické zapuštění do dvojitého torusu je jednou ze sedmi pravidelných kubických map, u nichž je celkový počet vrcholů dvojnásobkem počtu vrcholů ploch [13] . Mezi sedmi symetrickými zobecněnými Petersenovými grafy jsou kubický graf , Petersenův graf , dvanáctistěnný graf , Desarguesův graf a Naurův graf . $G(n,k)$ $n=10$ $k=2$ $k^{2}=\pm 1{\pmod {n))$ $(n,k)\in \{(4,1),(5,2),(8,3),(10,2),(10,3),(12,5),(24) ,5)\}$ $G(4;1)$ $G(5;2)$ $G(10;2)$ $G(10;3)$ $G(12,5)$

Charakteristický polynom Möbiova-Cantorova grafu je roven:

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

Poznámky

↑ Möbius, 1828 .
↑ Kantor, 1882 .
↑ Coxeter, 1950 .
↑ OEIS sekvence A110507 _
↑ Dan McQuillan, R. Bruce Richter. O počtu křížení určitých zobecněných Petersenových grafů // Diskrétní matematika. - 1992. - T. 104 , no. 3 . — S. 311–320 . - doi : 10.1016/0012-365X(92)90453-M .
↑ 1 2 Marushich, Pisansky, 2000 .
↑ Threlfall, 1932 .
↑ Tucker, 1984 .
↑ Leinen, Kuellmans, 2004 .
↑ Royle, G. F016A data (downlink)
↑ Conder, M. , Dobcsányi, P. "Trivalentní symetrické grafy až do 768 vrcholů." J. Combin. Matematika. Kombajn. Počítat. 40, 41-63, 2002
↑ Frucht, Graver, Watkins 1971 .
↑ McMullen, 1992 .

Odkazy

HSM Coxeter. Samoduální konfigurace a pravidelné grafy // Bulletin American Mathematical Society . - 1950. - T. 56 , čís. 5 . — S. 413–455 . - doi : 10.1090/S0002-9904-1950-09407-5 .
R. Frucht, J. E. Graver, M. E. Watkins. Skupiny zobecněných Petersenových grafů // Proceedings of the Cambridge Philosophical Society . - 1971. - T. 70 , čís. 02 . — S. 211–218 . - doi : 10.1017/S0305004100049811 .
S. Kantor. Über die Configurationen (3, 3) mit den Indexs 8, 9 und ihren Zusammenhang mit den Curven dritter Ordnung // Sitzungsberichte der Mathematisch-Naturwissenschaftlichen Classe der Kaiserlichen Akademie der Wissenschaften, Wien. - 1882. - T. 84 , čís. 1 . — S. 915–932 . .
E. Lijnen, A. Ceulemans. Orientované 2-buňkové vložení grafu a jejich klasifikace symetrie: Generování algoritmů a případová studie Möbiova-Kantorova grafu // J. Chem. inf. Počítat. Sci .. - 2004. - T. 44 , no. 5 . - S. 1552-1564 . doi : 10.1021 / ci049865c . — PMID 15446812 .
Dragan Marušic, Tomaž Pisanski. Pozoruhodný zobecněný Petersenův graf G (8,3) // Math. Slováca. - 2000. - T. 50 . — S. 117–121 .
Peter McMullen. Pravidelný mnohostěn typu { p , 3} se 2 p vrcholy // Geometriae Dedicata . - 1992. - T. 43 , no. 3 . — S. 285–289 . - doi : 10.1007/BF00151518 .
AF Mobius. Kann von zwei dreiseitigen Pyramiden eine jede in Bezug auf die andere um- und eingeschrieben zugleich heissen? // J. Reine Angew. Matematika. . - 1828. - T. 3 . — S. 273–278 . . V Gesammelte Werke (1886), svazek 1, strany 439-446.
Thomas W. Tucker. Existuje pouze jedna skupina rodu dva // Journal of Combinatorial Theory, Series B. - 1984. - V. 36 , no. 3 . — S. 269–275 . - doi : 10.1016/0095-8956(84)90032-7 .
W. Threlfall. Gruppenbilder // Abhandlungen der Mathematisch-Physischen Klasse der Sächsischen Akademie der Wissenschaften. - 1932. - T. 41 , čís. 6 . — S. 1–59 . .
Odhalení sochy.

Externí odkazy

Weisstein, Eric W. Möbius-Kantor Graph (anglicky) na webových stránkách Wolfram MathWorld .
Weisstein, Eric W. Möbius-Kantor Configuration (anglicky) na webu Wolfram MathWorld .