Hrabě z Nauru

hrabě z Nauru
Vrcholy 24
žebra 36
Poloměr čtyři
Průměr čtyři
obvod 6
Automorfismy 144 ( S4 × S3 )
Chromatické číslo 2
Chromatický index 3
Vlastnosti

kubický
symetrický
Hamiltonův
bipartitní
Cayleyův graf


Celý
 Mediální soubory na Wikimedia Commons

V teorii grafů  je Nauruův graf symetrický bipartitní kubický graf s 24 vrcholy a 36 hranami. Hrabě byl pojmenován Epsteinem po dvanácticípé hvězdě na vlajce Nauru . [jeden]

Barevné číslo grafu je 2, chromatický index je 3, průměr je 4, poloměr  je 4 a obvod je 6 [2] . Graf je spojen 3 vrcholy a 3 hranami .

Nejmenší kubické grafy s kříženími 1-8 jsou známy (sekvence A110507 v OEIS ). Nejmenší graf s 8 kříženími je graf Nauru. Existuje 5 neizomorfních kubických grafů s 24 vrcholy a 8 průsečíky [3] . Jedním z nich je Count McGee , také známý jako (3-7) -cell . [čtyři]

Konstrukce

Nauruův graf je hamiltonovský a lze jej popsat pomocí LCF notace  : [5, −9, 7, −7, 9, −5] 4 . [jeden]

Naurův graf lze také zkonstruovat jako zobecněný Petersenův graf G (12, 5) tvořený vrcholy dvanáctiúhelníku , kde hrany spojují vrcholy tak, aby vytvořily 12paprskovou hvězdu spojením vrcholů s krokem 5.

Je také možná konstrukce založená na kombinatorice . Vezmeme tři různé předměty a dáme je do čtyř nerozeznatelných krabic, ne více než jeden předmět na krabici. Existuje 24 způsobů umístění objektů, což odpovídá 24 vrcholům grafu. Pokud je možné se přesunout z jednoho umístění do druhého přesunem právě jedné položky do prázdného boxu, spojíme dva vrcholy hranou. Výsledným grafem přechodu z polohy do polohy je graf Nauru.

Algebraické vlastnosti

Grupa automorfismu Nauruova grafu je grupa řádu 144. [5] . Grupa je izomorfní k přímému součinu symetrických grup S 4 a S 3 a působí tranzitivně na vrcholy, hrany a oblouky grafu. Nauruův graf je tedy symetrický (i když není tranzitivní na vzdálenost ). Graf má automorfismy, které mapují jakýkoli vrchol na jakýkoli jiný a jakoukoli hranu na jakoukoli jinou. Podle Fosterova seznamu je Nauruův graf jediným kubickým symetrickým grafem s 24 vrcholy [2] .

Zobecněný Petersenův graf G ( n, k ) je vertexově tranzitivní právě tehdy, když n  = 10 ak =  2 nebo pokud k 2  ≡ ±1 (mod  n ) a je hranově tranzitivní pouze tehdy, když: ( n, k ) = (4.1), (5.2), (8.3), (10.2), (10.3), (12.5), (24.5) [6] . Nauruův graf je tedy jedním ze sedmi symetrických zobecněných Petersenových grafů. Těchto sedm grafů zahrnuje kubický graf , Petersenův graf , Möbiův–Cantorův graf , dvanáctistěnný graf a Desarguesův graf .

Nauruův graf je Cayleyův graf skupiny S 4 , symetrické čtyřprvkové permutační grupy vzniklé permutací prvního prvku třemi dalšími: (1 2), (1 3) a (1 4).

Charakteristickým polynomem matice grafu Nauru je

z čehož plyne, že graf je celé číslo —  graf, jehož spektrum se skládá pouze z celých čísel.

Topologické vlastnosti

Graf Nauru má dvě různá vložení jako zobecněný pravidelný mnohostěn , ve kterém jsou topologické povrchy rozděleny na hrany, vrcholy a plochy takovým způsobem, že existuje symetrie, která přijímá jakýkoli příznak (dopadající trojice vrcholu, hrany, a obličej) k jakékoli jiné vlajce [7] .

Jedno z těchto dvou vložení tvoří torus , takže Nauruův graf je toroidní graf  — skládá se z 12 šestiúhelníkových ploch spolu s 24 vrcholy a 36 plochami Nauruových grafů. Duální graf tohoto vložení je symetrický 6-pravidelný graf s 12 vrcholy a 36 hranami.

Další symetrické vložení grafu Nauru má šest dvanáctiúhelníkových ploch a tvoří plochu rodu 4. Jeho duální graf není jednoduchý graf , protože každá plocha sdílí tři hrany se čtyřmi dalšími plochami, ale je to multigraf . Tento duální graf lze vytvořit z grafu pravidelného osmistěnu nahrazením každé hrany třemi rovnoběžnými hranami.

Sada ploch jednoho z těchto dvou vložení je sadou Petriho polygonů druhého vložení.

Geometrické vlastnosti

Stejně jako všechny zobecněné Petersenovy grafy lze i Nauruův graf reprezentovat jako body v rovině tak, že sousední vrcholy jsou ve vzdálenosti jedné. Jedná se tedy o jednotkový graf vzdálenosti [8] . Tento graf a hranol jsou jediné zobecněné Petersenovy grafy G ( n , p ), které nelze znázornit tak, aby symetrie vzoru tvořily cyklickou grupu řádu n . Místo toho má jeho grafová reprezentace jako grupu symetrie dihedrální grupu Dih 6 .

Historie

První, kdo napsal o grafu Nauru, byl Foster, který graf zařadil do seznamu všech kubických symetrických grafů [9] . Úplný seznam kubických symetrických grafů je nyní pojmenován po něm ( Foster's List ) a v tomto seznamu je počet Nauru očíslován F24A, ale nemá žádné jméno [10] . V roce 1950 Coxeter zmínil graf podruhé, dal hamiltonovské znázornění pro ilustraci článku a popsal graf jako Leviho graf projektivní konfigurace objevené Zahariasem [11] [12] .

V roce 2003 napsal Ed Pegg Jr. v článku na webu Mathematical Association of America , že F24A si zaslouží jméno, ale nenavrhl žádné [13] . Nakonec v roce 2007 použil David Epstein jméno hrabě z Nauru, protože vlajka Republiky Nauru obsahuje 12cípou hvězdu, podobnou té, která se vyskytuje, když je graf sestaven jako zobecněný Petersenův graf. [jeden]

Poznámky

  1. ↑ 1 2 3 David Eppstein, The many faces of the Nauru graph Archivováno z originálu 21. července 2011. na LiveJournal, 2007.
  2. ↑ 1 2 Conder, Dobcsányi, 2002 , s. 40, 41-63.
  3. ↑ Pegg, Exoo, 2009 .
  4. ↑ Weisstein, Eric W. Graph Crossing Number  na webu Wolfram MathWorld .
  5. ↑ Royle, G. Data F024A Archivováno 6. března 2011 na Wayback Machine
  6. ↑ Frucht, Graver, Watkins, 1971 , str. 211–218.
  7. ↑ McMullen, 1992 , s. 285–289.
  8. ↑ 1 2 Žitník, Horvát, Pisanski, 2010 .
  9. ↑ Foster, 1932 , str. 309–317.
  10. ↑ Bouwer, Chernoff, Monson, Star, 1988 .
  11. ↑ Coxeter, 1950 , str. 413–455.
  12. ↑ Zacharias, 1941 , str. 147–170.
  13. ↑ Pegg, 2003 .

Literatura