Möbius Graph - Cantor

Möbius–Cantor-kaavio

Nimetty	August Ferdinand Möbius ja Z. Kantor
Huiput	16
kylkiluut	24
Säde	neljä
Halkaisija	neljä
Ympärysmitta	6
Automorfismit	96
Kromaattinen numero	2
Kromaattinen indeksi	3
Suku	yksi
Ominaisuudet	symmetrinen Hamiltonin bipartite kuutioyksikköetäisyys Cayley - graafi täydellinen yksinkertaisesti orientoitavissa

Möbius-Cantor-graafi on symmetrinen kaksiosainen kuutiograafi , jossa on 16 kärkeä ja 24 reunaa ja joka on nimetty August Ferdinand Möbiuksen ja Seligman Cantorin (1857–1903) mukaan. Se voidaan määritellä yleistetyksi Petersen -graafiksi, eli se muodostuu kahdeksankulmaiseen tähteen kytketyn kahdeksankulmion kärjestä, jossa jokainen piste on yhdistetty peräkkäin kolmanteen pisteeseen. $G(8,3)$

Möbius-Cantor-kokoonpano

Möbius vuonna 1828 [1] esitti kysymyksen monikulmion parin olemassaolosta, joissa kummassakin on sivut, sillä ominaisuudella, että yhden monikulmion kärjet sijaitsevat viivoilla, jotka kulkevat toisen monikulmion sivujen läpi ja päinvastoin. Jos tällainen pari on olemassa, näiden monikulmioiden kärkien ja sivujen on muodostettava projektiivinen konfiguraatio . Sillä euklidisella tasolla ei ole ratkaisua , mutta vuonna 1882 Kantor [2] löysi tämän tyyppisen monikulmion parin ongelman yleistyksessä, jossa pisteet ja reunat kuuluvat kompleksiseen projektitiiviseen tasoon , toisin sanoen Cantorin ratkaisussa. , monikulmion kärkien koordinaatit ovat kompleksilukuja . Cantorin ratkaisua toistensa sisäänkirjoitettujen nelikulmioiden parille kompleksisessa projektiotasossa kutsutaan Möbius-Cantor-konfiguraatioksi . Möbius-Kantor-graafi on saanut nimensä Möbius-Cantor-konfiguraatiosta, koska se on tämän konfiguraation Levi-graafi . Graafissa on yksi kärki kullekin konfiguraatiopisteelle ja yksi piste jokaiselle kolmiolle, ja reunat yhdistävät kaksi kärkeä, jos yksi kärki vastaa pistettä ja toinen kolmoispistettä, joka sisältää kyseisen pisteen. $s$ $p=4$ $p=4$

Suhde hyperkuutioon

Möbius-Cantor-graafi on neliulotteisen hyperkuutiograafin aligraafi, ja se muodostetaan poistamalla kahdeksan reunaa hyperkuutiosta [3] . Koska hyperkuutio on yksikköetäisyysgraafi , Möbius-Cantor-graafi voidaan piirtää myös tasoon, jossa kaikki sivut ovat yksikköpituisia, vaikka tällainen esitys johtaisi reunojen risteytymiseen.

Topologia

Möbius-Cantor-graafia ei voi upottaa tasoon, jossa ei ole leikkauspisteitä, sen risteysluku on 4 ja se on pienin kuutiograafi, jolla on näin paljon risteyksiä [4] . Lisäksi graafi antaa esimerkin graafista, jonka kaikkien aligraafien leikkauspisteiden määrä on kaksi tai useampi erilainen kuin itse graafin leikkauspisteiden määrä [5] . Se on kuitenkin toroidinen - siinä on sen upotus torukseen , jossa kaikki sen pinnat ovat kuusikulmio [6] . Tämän upotuksen kaksoiskaavio on hyperoktaedrikuvaaja . $K_{2,2,2,2}$

On olemassa vielä symmetrisempi Möbius-Cantor-graafin upotus kaksoistorukseen , joka on säännöllinen kartta ja jossa on kuusi kahdeksankulmaista pintaa, jossa kaikki 96 graafin symmetriaa voidaan toteuttaa upotussymmetrioihin [7] . 96 elementin upotussymmetriaryhmässä on Cayley- graafi , joka voidaan upottaa kaksoistorukseen. Vuonna 1984 osoitettiin, että tämä on ainoa suvun kaksi ryhmä [8] .

DeWitt Godfreyn ja Duane Martinezin veistos kaksoistoruksen muodossa, jossa on upotettu Möbius-Kantor-graafi, oli esillä Slovenian teknisessä museossa kuudennessa Slovenian kansainvälisessä graafiteorian konferenssissa vuonna 2007. Vuonna 2013 veistoksen pyörivä versio oli näytteillä Colgaten yliopistossa .

Möbius-Cantor-graafi sallii upottamisen kolminkertaiseen torukseen (kolmannen tyyppinen torus), mikä antaa säännöllisen kartan , jossa on neljä 12-kulmaista pintaa; [6] .

Vuonna 2004 osana mahdollisten kemiallisten hiilirakenteiden tutkimusta tutkittiin Möbius-Cantor-graafin kaikkien upotusten perhettä kaksiulotteisissa monisäikeissä , minkä tuloksena osoitettiin, että ei-ekvivalentteja upotuksia on 759 [9] .

Algebralliset ominaisuudet

Möbius-Cantor-graafin automorfismiryhmä on luokkaa 96 oleva ryhmä [10] . Se toimii transitiivisesti pisteissä ja reunoissa, joten Möbius-Cantor-graafi on symmetrinen . Siinä on automorfismit, jotka kuvaavat minkä tahansa kärjen mihin tahansa toiseen ja minkä tahansa reunan mihin tahansa muuhun. Fosterin listan mukaan Möbius-Cantor-graafi on ainoa 16 kärjen symmetrinen graafi ja pienin kuutiosymmetrinen graafi, joka ei ole etäisyystransitiivinen [11] . Möbius-Cantor-graafi on myös Cayleyn graafi .

Yleistetty Petersen-graafi on huipputransitiivinen silloin ja vain jos ja , tai kun , ja reunatransitiivinen vain seuraavissa seitsemässä tapauksessa: [12] . Siten Möbius-Cantor-graafi on yksi näistä seitsemästä reunatransitiivisesta yleistetystä Petersen-graafista. Sen symmetrinen upottaminen kaksoistorukseen on yksi seitsemästä säännöllisestä kuutiokartasta, joissa pisteiden kokonaismäärä on kaksi kertaa pintapisteiden lukumäärä [13] . Seitsemän symmetrisen yleistetyn Petersen-graafin joukossa ovat kuutiograafi , Petersen- graafi , dodekaedrigraafi , Desargues-graafi ja Nauru-graafi . $G(n,k)$ $n = 10$ $k=2$ $k^{2}=\pm 1{\pmod {n))$ ${\näyttötyyli (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)$

Möbius-Cantor-graafin ominaispolynomi on yhtä suuri kuin:

{\näyttötyyli (x-3)(x-1)^{3}(x+1)^{3}(x+3)(x^{2}-3)^{4}.\ }

Muistiinpanot

↑ Möbius, 1828 .
↑ Kantor, 1882 .
↑ Coxeter, 1950 .
↑ OEIS - sekvenssi A110507 _
↑ Dan McQuillan, R. Bruce Richter. Tiettyjen yleistettyjen Petersen-graafien risteysluvuista // Discrete Mathematics. - 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. "Trivalent Symmetric Graphs Jopa 768 Vertices." J. Combin. Matematiikka. Yhdistää. Comput. 40, 41-63, 2002
↑ Frucht, Graver, Watkins 1971 .
↑ McMullen, 1992 .

Linkit

HSM Coxeter. Itsenäiset kaksoiskokoonpanot ja säännölliset kaaviot // Bulletin of the American Mathematical Society . - 1950. - T. 56 , no. 5 . — S. 413–455 . - doi : 10.1090/S0002-9904-1950-09407-5 .
R. Frucht, J. E. Graver, M. E. Watkins. Yleistettyjen Petersen-graafien ryhmät // Proceedings of the Cambridge Philosophical Society . - 1971. - T. 70 , no. 02 . — S. 211–218 . - doi : 10.1017/S0305004100049811 .
S. Kantor. Yber die Configurationen (3, 3) mit den indeksit 8, 9 und ihren Zusammenhang mit den Curven dritter Ordnung // Sitzungsberichte der Mathematisch-Naturwissenschaftlichen Classe der Kaiserlichen Akademie der Wissenschaften, Wien. - 1882. - T. 84 , no. 1 . — S. 915–932 . .
E. Lijnen, A. Ceulemans. Graafin suuntautuneet 2-soluiset upotukset ja niiden symmetrialuokitus: Algoritmien luominen ja Möbius-Kantor-graafin tapaustutkimus // J. Chem. inf. Comput. Sci .. - 2004. - T. 44 , no. 5 . - S. 1552-1564 . doi : 10.1021 / ci049865c . — PMID 15446812 .
Dragan Marušic, Tomaž Pisanski. Merkittävä yleistetty Petersen-graafi G (8,3) // Math. Slovakia. - 2000. - T. 50 . — S. 117–121 .
Peter McMullen. Tyypin { p , 3} säännöllinen polyhedra, jossa on 2 p - pistettä // 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. Matematiikka. . - 1828. - T. 3 . — S. 273–278 . . Teoksessa Gesammelte Werke (1886), osa 1, sivut 439-446.
Thomas W. Tucker. Sukua kaksi on vain yksi ryhmä // 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 , no. 6 . - S. 1-59 . .
Veistoksen paljastaminen.

Ulkoiset linkit

Weisstein, Eric W. Möbius-Kantor Graph (englanniksi) Wolfram MathWorld -verkkosivustolla .
Weisstein, Eric W. Möbius-Kantor Configuration (englanniksi) Wolfram MathWorld -verkkosivustolla .