Möbius – Kantorův graf - Möbius–Kantor graph

Möbius – Kantorův graf
Pojmenoval podle	August Ferdinand Möbius a S. Kantor
Vrcholy	16
Hrany	24
Poloměr	4
Průměr	4
Obvod	6
Automorfismy	96
Chromatické číslo	2
Chromatický index	3
Rod	1
Tloušťka knihy	3
Číslo fronty	2
Vlastnosti	Symetrický; Hamiltonian; Bipartitní; Krychlový; Jednotková vzdálenost; Cayleyův graf; Perfektní; Orientačně jednoduché
	Tabulka grafů a parametrů

V matematický pole teorie grafů, Möbius – Kantorův graf je symetrický bipartitní kubický graf s 16 vrcholy a 24 hranami pojmenovanými podle August Ferdinand Möbius a Seligmann Kantor. Lze jej definovat jako zobecněný Petersenův graf G(8,3): to znamená, že je tvořen vrcholy an osmiúhelník, spojený s vrcholy osmibodové hvězdy, ve které je každý bod hvězdy spojen s body tři kroky od ní.

Konfigurace Möbius – Kantor

Konfigurace Möbius – Kantor.

Möbius (1828) zeptal se, zda existuje pár mnohoúhelníky s str každá strana, která má vlastnost, že vrcholy jednoho polygonu leží na úsečkách procházejících hranami druhého mnohoúhelníku, a naopak. Pokud ano, vrcholy a hrany těchto polygonů by tvořily a projektivní konfigurace. Pro str = 4 v Euklidovské letadlo, ale Kantor (1882) našel dvojice polygonů tohoto typu, pro zobecnění problému, ve kterém body a hrany patří k složitá projektivní rovina. To znamená, že v Kantorově řešení jsou souřadnice vrcholů mnohoúhelníku komplexní čísla. Kantorovo řešení pro str = 4, dvojice vzájemně zapsaných čtyřúhelníků v komplexní projektivní rovině, se nazývá Konfigurace Möbius – Kantor. Graf Möbius – Kantor odvozuje svůj název od toho, že je Leviho graf konfigurace Möbius – Kantor. Má jeden vrchol na bod a jeden vrchol na trojnásobek, přičemž hrana spojuje dva vrcholy, pokud odpovídají bodu a trojici, která tento bod obsahuje.

Konfiguraci lze také popsat algebraicky z hlediska abelianská skupina ${displaystyle mathbb {Z} _ {3} imes mathbb {Z} _ {3}}$ s devíti prvky. Tato skupina má čtyři podskupiny řádu tři (podmnožiny prvků formuláře ${displaystyle (i, 0)}$ , ${displaystyle (i, i)}$ , ${displaystyle (i, 2i)}$ , a ${displaystyle (0, i)}$ z nichž každý lze použít k rozdělení devíti skupinových prvků na tři kosety tří prvků na coset. Těchto devět prvků a dvanáct kosetů tvoří konfiguraci, Hesseova konfigurace. Odstranění nulového prvku a čtyř kosetů obsahujících nulu vede ke konfiguraci Möbius – Kantor.

Jako podgraf

Graf Möbius – Kantor je a podgraf čtyřrozměrného hyperkrychlový graf, vytvořený odstraněním osmi hran z hyperkrychle (Coxeter 1950 ). Protože hyperkrychle je a graf jednotkové vzdálenosti, graf Möbius – Kantor lze také nakreslit v rovině se všemi jednotkami délky hran, i když takový výkres bude nutně mít pár dvojic hran.

Graf Möbius-Kantor se také vyskytuje mnohokrát jako v indukovaném podgrafu Hoffman – Singletonův graf. Každý z těchto případů je ve skutečnosti vlastní vektor Hoffman-Singletonova grafu s přidruženým vlastním číslem -3. Každý vrchol ne v indukovaném grafu Möbius – Kantor sousedí s přesně čtyřmi vrcholy v graf Möbius – Kantor, každý dva v polovině a bipartice grafu Möbius – Kantor.

Topologie

Graf Möbius – Kantor, vložený do torusu. Okraje táhnoucí se nahoru od centrálního čtverce by měly být považovány za spojovací s odpovídající hranou táhnoucí se dolů od čtverce a hrany vybíhající vlevo od čtverce by měly být považovány za spojovací s odpovídající hranou táhnoucí se vpravo.

Graf Möbius – Kantor nelze vložit bez křížení v rovině; má to číslo křížení 4 a je nejmenší kubický graf s tímto křížením (sekvence A110507 v OEIS ). Kromě toho poskytuje příklad grafu, jehož čísla křížení podgrafů se od něj liší o dva nebo více.^[1]Je to však a toroidní graf: má zabudování do torus ve kterém jsou všechny tváře šestiúhelníky (Marušič & Pisanski 2000 ). The duální graf tohoto vložení je hyperoktaedrický graf K._2,2,2,2.

Ještě více symetrické vložení grafu Möbius – Kantor do dvojitý torus což je běžná mapa se šesti osmiúhelníkový plochy, ve kterých lze všech 96 symetrií grafu realizovat jako symetrie vložení; Coxeter (1950) připíše toto vložení Threlfall (1932). Jeho 96 prvků skupina symetrie má Cayleyův graf který může být sám vložen do dvojitého torusu, a byl zobrazen Tucker (1984) být jedinečnou skupinou s rod dva. Cayleyův graf na 96 vrcholech je vlajkový graf pravidelné mapy rodu 2, který má jako kostru Möbiova-Kantorova graf. To znamená, že ji lze získat z běžné mapy jako kostru duálu jejího barycentrického dělení. Socha od DeWitt Godfrey a Duane Martinez zobrazující dvojité torusové zakotvení symetrií grafu Möbius – Kantor bylo odhaleno v Technickém muzeu Slovinsko v rámci 6. slovinské mezinárodní konference o teorii grafů v roce 2007. V roce 2013 byla odhalena rotující verze sochy na Colgate University.

Graf Möbius – Kantor připouští vložení do a trojitý torus (rod 3 torus) to je a běžná mapa se čtyřmi 12-úhlovými tvářemi a je Petrie dual výše popsaného vložení dvojitého torusu; (Marušič & Pisanski 2000 ).

Lijnen & Ceulemans (2004), motivovaný zkoumáním potenciálních chemických struktur sloučenin uhlíku, studoval rodinu všech vložení grafu Möbius – Kantor na 2-rozdělovače; ukázali, že existuje 759 nerovnocenných vložení.

Algebraické vlastnosti

Skupina automorfismu Möbiova-Kantorova grafu je skupina řádu 96.^[2] Působí přechodně na vrcholy, na hrany a na oblouky grafu. Graf Möbius – Kantor je tedy a symetrický graf. Má automatorfismy, které berou jakýkoli vrchol na jakýkoli jiný vrchol a jakoukoli hranu na jakoukoli jinou hranu. Podle Podporovat sčítání lidu, Möbius – Kantorův graf je jedinečný kubický symetrický graf se 16 vrcholy a nejmenší kubický symetrický graf, který také není vzdálenost-tranzitivní.^[3] Graf Möbius – Kantor je také a Cayleyův graf.

Zobecněný Petersenův graf G(n, k) je vrcholem tranzitivní právě tehdy n = 10 a k = 2 nebo pokud k² ≡ ± 1 (modn) a je hraniční tranzitivní pouze v následujících sedmi případech: (n, k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5) nebo (24,5) (Frucht, Graver & Watkins 1971 ). Graf Möbius – Kantor je tedy jedním z pouhých sedmi symetrických generalizovaných Petersenových grafů. Jeho symetrické vložení dvojitého torusu je odpovídajícím způsobem jedním z pouhých sedmi pravidelných kubických map, ve kterých je celkový počet vrcholů dvakrát větší než počet vrcholů na plochu (McMullen 1992 ). Mezi sedmi symetrickými zobecněnými Petersenovými grafy jsou krychlový graf ${displaystyle G (4,1)}$ , Petersenův graf ${displaystyle G (5,2)}$ , dodekahedrální graf ${displaystyle G (10,2)}$ , Desargues graf ${displaystyle G (10,3)}$ a Nauru graf ${displaystyle G (12,5)}$ .

The charakteristický polynom grafu Möbius – Kantor se rovná

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

Viz také

Skupina Pauli

Poznámky

^ McQuillan, Dan; Richter, R. Bruce (1992), „O číslech křížení určitých zobecněných Petersenových grafů“, Diskrétní matematika, 104 (3): 311–320, doi:10.1016 / 0012-365X (92) 90453-M, PAN 1171327.
^ Royle, G. Data F016A^{[trvalý mrtvý odkaz ]}
^ Conder, M. a Dobcsányi, P. „Trivalentní symetrické grafy až do 768 vrcholů.“ J. Combin. Matematika. Kombinovat. Comput. 40, 41-63, 2002.

Reference

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.
Frucht, Robert; Graver, Jack E .; Watkins, Mark E. (1971), „Skupiny zobecněných Petersenových grafů“, Sborník Cambridge Philosophical Society, 70 (02): 211–218, doi:10.1017 / S0305004100049811, PAN 0289365.
Kantor, Seligmann (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, Vídeň, 84 (1): 915–932.
Lijnen, Erwin; Ceulemans, Arnout (2004), „Oriented 2-Cell Embeddings of a Graph and their Symetry Classification: Generating Algorithms and Case Study of the Möbius-Kantor Graph“, Journal of Chemical Information and Modeling, 44 (5): 1552–1564, doi:10.1021 / ci049865c, PMID 15446812.
Marušič, Dragan; Pisanski, Tomaž (2000), „Pozoruhodný zobecněný Petersenův graf G(8,3)", Mathematica Slovaca, 50: 117–121.
McMullen, Peter (1992), „Pravidelný mnohostěn typu {str, 3} s 2str vrcholy ", Geometriae Dedicata, 43 (3): 285–289, doi:10.1007 / BF00151518.
Möbius, August Ferdinand (1828), „Kann von zwei dreiseitigen Pyramiden eine jede v Bezug auf die andere um- und eingeschrieben zugleich heissen?“ (PDF), Journal für die reine und angewandte Mathematik, 3: 273–278. v Gesammelte Werke (1886), sv. 1, s. 439–446.
Tucker, Thomas W. (1984), „Existuje pouze jedna skupina rodu dva“, Journal of Combinatorial Theory, Series B, 36 (3): 269–275, doi:10.1016/0095-8956(84)90032-7.
Threlfall, William (1932), "Gruppenbilder", Abhandlungen der Mathematisch-Physischen Klasse der Sächsischen Akademie der Wissenschaften, 41 (6): 1–59.
Jessica Wolz, Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018

externí odkazy

[1] McQuillan, Dan; Richter, R. Bruce (1992), „O číslech křížení určitých zobecněných Petersenových grafů“, Diskrétní matematika, 104 (3): 311–320, doi:10.1016 / 0012-365X (92) 90453-M, PAN 1171327.

[2] Royle, G. Data F016A^{[trvalý mrtvý odkaz ]}

[COND-3] Conder, M. a Dobcsányi, P. „Trivalentní symetrické grafy až do 768 vrcholů.“ J. Combin. Matematika. Kombinovat. Comput. 40, 41-63, 2002.

[1]

[2]

[3]