Nauru grófja

Nauru grófja
Csúcsok 24
borda 36
Sugár négy
Átmérő négy
Heveder 6
Automorfizmusok 144 ( S4 × S3 )
Kromatikus szám 2
Kromatikus index 3
Tulajdonságok

köbös
szimmetrikus
Hamiltoni
bipartit
Cayley-gráf


egész
 Médiafájlok a Wikimedia Commons oldalon

A gráfelméletben a Nauru gráf  egy szimmetrikus bipartit köbös gráf, 24 csúcsgal és 36 éllel. A grófot David Epstein a Nauru zászlaján lévő tizenkétágú csillagról nevezte . [egy]

A gráf kromatikus száma 2, kromatikus indexe 3, átmérője 4, sugara  4, kerülete 6 [2] . A gráf 3 csúcshoz és 3 élhez kapcsolódik .

Ismeretesek a legkisebb köbös grafikonok 1-8 keresztezésekkel ( A110507 szekvencia az OEIS -ben ). A legkisebb gráf 8 keresztezéssel a Nauru gráf. 5 nem izomorf köbös gráf létezik 24 csúcsgal és 8 metszésponttal [3] . Egyikük McGee gróf , más néven (3-7) -cell . [négy]

Épület

A Nauru gráf Hamilton -féle , és az LCF jelöléssel írható le  : [5, −9, 7, −7, 9, −5] 4 . [egy]

A Nauru gráf megszerkeszthető általánosított Petersen G (12, 5) gráfként is, amelyet egy kétszög csúcsai alkotnak , ahol élek kötik össze a csúcsokat, és egy 12 sugarú csillagot alkotnak, a csúcsokat 5-ös lépéssel összekötve.

Kombinatorika alapú konstrukció is lehetséges . Vegyünk három különböző tárgyat, és helyezzük őket négy megkülönböztethetetlen dobozba, dobozonként legfeljebb egy tárgyat. Az objektumok elhelyezésének 24 módja van, ami 24 gráfcsúcsnak felel meg. Ha lehetséges úgy mozogni egyik helyről a másikra, hogy pontosan egy elemet helyez át egy üres dobozba, akkor két csúcsot összekötünk éllel. Az eredményül kapott hely-hely átmenet gráf a Nauru gráf.

Algebrai tulajdonságok

A Nauru gráf automorfizmuscsoportja egy 144. rendű csoport [5] . A csoport izomorf az S 4 és S 3 szimmetrikus csoportok közvetlen szorzatával , és tranzitív módon hat a gráf csúcsaira, éleire és íveire. Így a Nauru gráf szimmetrikus (bár nem távolságtranzitív ). A gráfnak 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 Nauru gráf az egyetlen köbös szimmetrikus gráf, amelynek 24 csúcsa van [2] .

Egy általánosított Petersen-gráf G ( n, k ) akkor és csak akkor csúcstranzitív , ha n  = 10 és k  =2, vagy ha k 2  ≡ ±1 (mod  n ), és csak akkor éltranzitív , ha: ( n, k ) = (4.1), (5.2), (8.3), (10.2), (10.3), (12.5), (24.5) [6] . Így a Nauru-gráf a hét szimmetrikus általánosított Petersen-gráf egyike. Ez a hét gráf tartalmazza a köbös gráfot , a Petersen -gráfot , a Möbius–Cantor-gráfot , a dodekaéder gráfot és a Desargues-gráfot .

A Nauru gráf az S 4 csoport Cayley-gráfja, egy szimmetrikus négyelemes permutációs csoport, amely az első elem három másik elemmel való permutációjával jön létre: (1 2), (1 3) és (1 4).

A Nauru gráfmátrix karakterisztikus polinomja az

ebből következik, hogy a gráf egész szám – olyan  gráf, amelynek spektruma csak egész számokból áll.

Topológiai tulajdonságok

A Nauru gráfnak két különböző beágyazása van általánosított szabályos poliéderként , amelyben a topológiai felületek élekre, csúcsokra és lapokra vannak osztva oly módon, hogy létezik egy szimmetria, amely bármilyen zászlót felvesz (egy csúcs beeső hármasa, él, és arc) bármely más zászlóra [7] .

E két beágyazás egyike egy tóruszt alkot , tehát a Nauru gráf egy toroid gráf  – 12 hatszögletű lapból, valamint 24 csúcsból és 36 lapos Nauru gráfból áll. Ennek a beágyazásnak a duális gráfja egy szimmetrikus 6-reguláris gráf, 12 csúcsgal és 36 éllel.

A Nauru gráf egy másik szimmetrikus beágyazása hat kétszögletű lappal rendelkezik, és egy 4. nemzetséghez tartozó felületet alkot . Duális gráfja nem egy egyszerű gráf , mivel mindegyik lapnak három éle van négy másik lappal, hanem egy multigráf . Ez a kettős gráf egy szabályos oktaéder gráfjából alakítható ki úgy, hogy minden élt három párhuzamos élre cserélünk.

E két beágyazás bármelyikének lapjainak halmaza a másik beágyazás Petri-sokszögeinek halmaza.

Geometriai tulajdonságok

Mint minden általánosított Petersen-gráf, a Nauru-gráf is ábrázolható pontokként a síkban oly módon, hogy a szomszédos csúcsok egy távolságra vannak. Így ez egy egységnyi távolsággráf [8] . Ez a gráf és a prizma az egyetlen olyan általánosított G ( n , p ) Petersen-gráf, amely nem ábrázolható úgy, hogy a minta szimmetriái n -rendű ciklikus csoportot alkotjanak . Ehelyett a gráfábrázolás szimmetriacsoportja a Dih 6 diédercsoport .

Történelem

Az első ember, aki Nauru gráfjáról írt, Foster volt, aki felvette a gráfot az összes köbös szimmetrikus gráfok listájára [9] . A köbös szimmetrikus gráfok teljes listája most róla van elnevezve ( Foster's List ), és ebben a listában Nauru grófja F24A számmal van ellátva, de nem kap semmilyen nevet [10] . 1950-ben Coxeter másodszor említette a gráfot, hamiltoni reprezentációt adva a papír szemléltetésére, és a gráfot a Zaharias által felfedezett projektív konfiguráció Levi -gráfjaként írja le [11] [12] .

2003-ban Ed Pegg Jr. az Amerikai Mathematical Association honlapján megjelent cikkében azt írta, hogy az F24A megérdemel egy nevet, de nem javasolta [13] . Végül 2007-ben David Epstein a Nauru grófja nevet használta, mivel a Nauru Köztársaság zászlaja egy 12 ágú csillagot tartalmaz, hasonlóan ahhoz, amely akkor fordul elő, amikor a gráfot általánosított Petersen-gráfként szerkesztik. [egy]

Jegyzetek

  1. 1 2 3 David Eppstein, A Nauru-gráf sok arca Archiválva az eredetiből 2011. július 21-én. a LiveJournalon, 2007.
  2. 1 2 Conder, Dobcsányi, 2002 , p. 40, 41-63.
  3. Pegg, Exoo, 2009 .
  4. Weisstein, Eric W. Graph Crossing Number  a Wolfram MathWorld webhelyén .
  5. Royle, G. F024A adatok archiválva : 2011. március 6. a Wayback Machine -nél
  6. Frucht, Graver, Watkins, 1971 , p. 211–218.
  7. McMullen, 1992 , p. 285–289.
  8. 1 2 Zitnik, Horvat, Pisanski, 2010 .
  9. Foster, 1932 , p. 309–317.
  10. Bouwer, Chernoff, Monson, Star, 1988 .
  11. Coxeter, 1950 , p. 413–455.
  12. Zakariás, 1941 , p. 147–170.
  13. Pegg, 2003 .

Irodalom