Möbius Graph - Kántor

Möbius–Cantor gráf

Valaki után elnevezve	August Ferdinand Möbius és Z. Kantor
Csúcsok	16
borda	24
Sugár	négy
Átmérő	négy
Heveder	6
Automorfizmusok	96
Kromatikus szám	2
Kromatikus index	3
Nemzetség	egy
Tulajdonságok	szimmetrikus Hamiltoni bipartite köbös egység távolság Cayley gráf tökéletes egyszerűen tájékozható

A Möbius-Cantor gráf egy szimmetrikus kétrészes köbös gráf 16 csúcsgal és 24 éllel, August Ferdinand Möbius és Seligman Cantor (1857–1903) nevéhez fűződik. Általánosított Petersen-gráfként definiálható , azaz egy nyolcszögletű csillaghoz kapcsolt nyolcszög csúcsai alkotják, amelyben minden pont a sorban a harmadik ponthoz kapcsolódik . $G(8,3)$

Möbius-Cantor konfiguráció

Möbius 1828-ban [1] felvetette egy olyan sokszögpár létezését, amelyek mindegyikében oldalak vannak, azzal a tulajdonsággal, hogy az egyik sokszög csúcsai a másik oldalain átmenő egyeneseken fekszenek, és fordítva. Ha létezik ilyen pár, akkor ezen sokszögek csúcsainak és oldalainak projektív konfigurációt kell alkotniuk . Az euklideszi síkon ugyanis nincs megoldás , de 1882-ben Kantor [2] talált egy ilyen típusú sokszögpárt a probléma általánosításában, amelyben a pontok és élek a komplex projektív síkhoz tartoznak , vagyis Cantor megoldásában. , a sokszög csúcsainak koordinátái komplex számok . A komplex projektív síkban egymásra írt négyszögpár Cantor-féle megoldását Möbius-Cantor konfigurációnak nevezzük . A Möbius-Kantor gráf a nevét a Möbius-Cantor konfigurációról kapta, mivel ennek a konfigurációnak a Levi gráfja . A gráfnak minden konfigurációs ponthoz egy csúcsa van, és minden hármashoz egy pontja van, és az élek két csúcsot kötnek össze, ha az egyik csúcs egy pontnak, a másik pedig az azt a pontot tartalmazó hármasnak felel meg. $p$ $p=4$ $p=4$

Kapcsolat a hiperkockával

A Möbius-Cantor gráf a négydimenziós hiperkocka gráf részgráfja, és a hiperkocka nyolc élének eltávolításával jön létre [3] . Mivel a hiperkocka egységnyi távolsággráf , ezért a Möbius-Cantor gráf minden egységnyi hosszúságú oldallal is megrajzolható a síkban, bár egy ilyen ábrázolás élek keresztezését eredményezné.

Topológia

A Möbius-Cantor gráf nem ágyazható síkba metszéspontok nélkül, keresztezési száma 4, és ez a legkisebb köbös gráf ekkora keresztezéssel [4] . Ezenkívül a gráf példát ad egy gráfra, amelynek minden részgráfjában a metszéspontok száma kettő vagy több különbözik magának a gráfnak a metszéspontjainak számától [5] . Azonban toroid alakú – ott van a tóruszba való beágyazódása , amelyben minden lapja hatszög [6] . Ennek a beágyazásnak a kettős gráfja a hiperoktaéder gráf . $K_{2,2,2,2}$

Létezik még szimmetrikusabb beágyazása a Möbius-Cantor gráfnak a kettős tóruszba , amely egy szabályos leképezés és hat nyolcszöglappal rendelkezik, amelyben mind a 96 gráfszimmetria megvalósítható beágyazási szimmetriaként [7] . A 96 elemből álló beágyazó szimmetriacsoportnak van a Cayley-gráfja , amely kettős tóruszba ágyazható. 1984-ben kimutatták, hogy ez a kettes nemzetség egyetlen csoportja [8] .

DeWitt Godfrey és Duane Martinez kettős tórusz formájában , beágyazott Möbius-Kantor gráfral alkotott szobrát a Szlovéniai Műszaki Múzeumban állították ki 2007-ben a 6. szlovén nemzetközi gráfelméleti konferencián. 2013-ban a szobor forgó változatát a Colgate Egyetemen állították ki .

A Möbius-Cantor gráf beágyazódik a hármas tóruszba (a harmadik típusú tórusz), ami egy szabályos térképet ad négy 12 szögű lappal; [6] .

2004-ben a lehetséges kémiai szénszerkezetek vizsgálata során a Möbius-Cantor gráf összes beágyazottságának családját tanulmányozták kétdimenziós sokaságban , ennek eredményeként kimutatták, hogy 759 nem egyenértékű beágyazás létezik [9] .

Algebrai tulajdonságok

A Möbius-Cantor gráf automorfizmuscsoportja egy 96-os rendű csoport [10] . Tranzitívan hat a csúcsokra és az élekre, így a Möbius-Cantor gráf szimmetrikus . Vannak olyan automorfizmusai, amelyek bármely csúcsot bármely másikhoz, és bármely élt bármely másikhoz leképeznek. Foster listája szerint a Möbius-Cantor gráf az egyetlen 16 csúcsú szimmetrikus gráf és a legkisebb köbös szimmetrikus gráf, amely nem távolságtranzitív [11] . A Möbius-Cantor gráf egyben Cayley gráfja is .

Egy általánosított Petersen -gráf akkor és csak akkor csúcstranzitív, ha és , vagy amikor , és csak az alábbi hét esetben éltranzitív: [12] . Így a Möbius-Cantor gráf a hét éltranzitív általánosított Petersen-gráf egyike. Szimmetrikus beágyazása a kettős tóruszba egyike annak a hét szabályos köbös leképezésnek, amelyeknél a csúcsok teljes száma kétszerese a lapcsúcsok számának [13] . A hét szimmetrikus általánosított Petersen-gráf közé tartozik a köbös gráf , a Petersen -gráf , a dodekaéder gráf , a Desargues-gráf és a Nauru-gráf . $G(n,k)$ $n=10$ $k=2$ $k^{2}=\pm 1{\pmod {n))$ ${\megjelenítési stílus (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)$

A Möbius-Cantor gráf karakterisztikus polinomja egyenlő:

{\megjelenítési stílus (x-3)(x-1)^{3}(x+1)^{3}(x+3)(x^{2}-3)^{4}.\ }

Jegyzetek

↑ Möbius, 1828 .
↑ Kantor, 1882 .
↑ Coxeter, 1950 .
↑ OEIS szekvencia A110507 _
↑ Dan McQuillan, R. Bruce Richter. Egyes általánosított Petersen-gráfok keresztezési számairól // Discrete Mathematics. - 1992. - T. 104 , sz. 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 adatok (lefelé irányuló kapcsolat)
↑ Conder, M. , Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Kombájn. Comput. 40, 41-63, 2002
↑ Frucht, Graver, Watkins 1971 .
↑ McMullen, 1992 .

Linkek

HSM Coxeter. Önkettős konfigurációk és szabályos gráfok // Bulletin of the American Mathematical Society . - 1950. - T. 56 , sz. 5 . – S. 413–455 . - doi : 10.1090/S0002-9904-1950-09407-5 .
R. Frucht, J. E. Graver, M. E. Watkins. Az általánosított Petersen-gráfok csoportjai // Proceedings of the Cambridge Philosophical Society . - 1971. - T. 70 , sz. 02 . – S. 211–218 . - doi : 10.1017/S0305004100049811 .
S. Kantor. Über die Configurationen (3, 3) mit den Index 8, 9 und ihren Zusammenhang mit den Curven dritter Ordnung // Sitzungsberichte der Mathematisch-Naturwissenschaftlichen Classe der Kaiserlichen Akademie der Wissenschaften, Wien. - 1882. - T. 84 , sz. 1 . – S. 915–932 . .
E. Lijnen, A. Ceulemans. Grafikonok orientált 2 cellás beágyazásai és szimmetriai osztályozásuk: Algoritmusok generálása és a Möbius-Kantor gráf esettanulmánya // J. Chem. inf. Comput. Sci .. - 2004. - T. 44 , sz. 5 . - S. 1552-1564 . doi : 10.1021 / ci049865c . — PMID 15446812 .
Dragan Marušic, Tomaž Pisanski. A figyelemre méltó általánosított Petersen-gráf G (8,3) // Math. Szlovákia. - 2000. - T. 50 . – S. 117–121 .
Peter McMullen. A { p , 3} típusú szabályos poliéderek 2 p csúcsával // Geometriae Dedicata . - 1992. - T. 43 , sz. 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. Math. . - 1828. - T. 3 . – S. 273–278 . . In Gesammelte Werke (1886), 1. kötet, 439-446.
Thomas W. Tucker. A kettes nemzetségnek csak egy csoportja van // 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 , sz. 6 . – S. 1–59 . .
A szobor leleplezése.

Külső linkek

Weisstein, Eric W. Möbius-Kantor Graph (angol) a Wolfram MathWorld webhelyén .
Weisstein, Eric W. Möbius-Kantor konfiguráció (angol) a Wolfram MathWorld webhelyen .