Contele de Nauru

Contele de Nauru
Vârfurile 24
coaste 36
Rază patru
Diametru patru
Circumferinţă 6
Automorfisme 144 ( S4 × S3 )
Număr cromatic 2
Indicele cromatic 3
Proprietăți

Graficul Cayley bipartit hamiltonian
simetric cubic



întreg
 Fișiere media la Wikimedia Commons

În teoria grafurilor, graful Nauru  este un graf cubic bipartit simetric cu 24 de vârfuri și 36 de muchii. Contele a fost numit David Epstein după steaua cu douăsprezece colțuri de pe steagul Nauruului . [unu]

Numărul cromatic al graficului este 2, indicele cromatic este 3, diametrul este 4, raza  este 4 și circumferința este 6 [2] . Graficul este conectat la 3 vârfuri și conectat la 3 muchii .

Sunt cunoscute cele mai mici grafice cubice cu încrucișările 1-8 (secvența A110507 în OEIS ). Cel mai mic grafic cu 8 încrucișări este graficul Nauru. Există 5 grafice cubice neizomorfe cu 24 de vârfuri și 8 intersecții [3] . Unul dintre ei este contele McGee , cunoscut și ca (3-7) -cell . [patru]

Clădire

Graficul Nauru este hamiltonian și poate fi descris folosind notația LCF  : [5, −9, 7, −7, 9, −5] 4 . [unu]

Graficul Nauru poate fi construit și ca un grafic Petersen generalizat G (12, 5) format din vârfurile unui dodecagon , unde marginile leagă vârfurile pentru a forma o stea cu 12 raze prin conectarea vârfurilor cu un pas de 5.

Este posibilă și o construcție bazată pe combinatorie . Să luăm trei obiecte diferite și să le punem în patru cutii care nu se pot distinge, nu mai mult de un obiect pe cutie. Există 24 de moduri de a plasa obiecte, ceea ce corespunde la 24 de vârfuri grafice. Dacă este posibil să treceți de la o plasare la alta prin mutarea exactă a unui element într-o casetă goală, conectăm două vârfuri cu o margine. Graficul de tranziție de la locație la locație rezultat este graficul Nauru.

Proprietăți algebrice

Grupul de automorfism al grafului Nauru este un grup de ordinul 144. [5] . Grupul este izomorf cu produsul direct al grupărilor simetrice S 4 și S 3 și acționează tranzitiv asupra vârfurilor, muchiilor și arcelor graficului. Astfel, graficul Nauru este simetric (deși nu este tranzitiv la distanță ). Graficul are automorfisme care mapează orice vârf cu oricare altul și orice margine cu oricare alta. Conform listei lui Foster, graficul Nauru este singurul grafic simetric cubic cu 24 de vârfuri [2] .

Un grafic Petersen generalizat G ( n, k ) este tranzitiv la vârf dacă și numai dacă n  = 10 și k  =2 sau dacă k 2  ≡ ±1 (mod  n ) și este tranzitiv la muchie numai dacă: ( n, k ) = (4.1), (5.2), (8.3), (10.2), (10.3), (12.5), (24.5) [6] . Astfel, graficul Nauru este unul dintre cele șapte grafice Petersen generalizate simetrice. Aceste șapte grafice includ graficul cubic , graficul Petersen , graficul Möbius–Cantor , graficul dodecaedru și graficul Desargues .

Graficul Nauru este graficul Cayley al grupului S 4 , un grup de permutare simetric de patru elemente format prin permutarea primului element cu alți trei: (1 2), (1 3) și (1 4).

Polinomul caracteristic al matricei graficului Nauru este

de unde rezultă că graficul este un număr întreg — un  grafic al cărui spectru este format numai din numere întregi.

Proprietăți topologice

Graficul Nauru are două înglobări diferite ca un poliedru regulat generalizat , în care suprafețele topologice sunt împărțite în muchii, vârfuri și fețe astfel încât să existe o simetrie care ia orice steag (triplu incident al unui vârf, muchie, și față) la orice alt steag [7] .

Una dintre aceste două înglobări formează un torus , deci graficul Nauru este un grafic toroidal  - constă din 12 fețe hexagonale împreună cu 24 de vârfuri și 36 de fețe grafice Nauru. Graficul dual al acestei încorporare este un grafic simetric cu 6 regulate cu 12 vârfuri și 36 de muchii.

O altă încorporare simetrică a graficului Nauru are șase fețe dodecagonale și formează o suprafață de gen 4. Graficul său dual nu este un simplu grafic , deoarece fiecare față împărtășește trei muchii cu alte patru fețe, dar este un multigraf . Acest grafic dual poate fi format din graficul unui octaedru regulat prin înlocuirea fiecărei muchii cu trei muchii paralele.

Setul de fețe ale oricăreia dintre aceste două înglobări este mulțimea poligoanelor Petri ale celeilalte înglobări.

Proprietăți geometrice

La fel ca toate graficele Petersen generalizate, graficul Nauru poate fi reprezentat ca puncte în plan în așa fel încât vârfurile adiacente să fie la o distanță de unu. Astfel, este un grafic de distanță unitară [8] . Acest grafic și prisma sunt singurele grafice Petersen generalizate G ( n , p ) care nu pot fi reprezentate în așa fel încât simetriile modelului să formeze un grup ciclic de ordinul n . În schimb, reprezentarea sa grafică are grupul diedric Dih 6 ca grup de simetrie .

Istorie

Prima persoană care a scris despre graficul din Nauru a fost Foster, care a enumerat graficul în lista tuturor graficelor simetrice cubice [9] . O listă completă de grafice simetrice cubice este acum numită după el ( Lista lui Foster ) și în această listă numărul de Nauru este numerotat F24A, dar nu i se dă niciun nume [10] . În 1950 Coxeter a menționat graficul pentru a doua oară, oferind o reprezentare hamiltoniană pentru a ilustra lucrarea și descriind graficul ca un grafic Levi al configurației proiective descoperite de Zaharias [11] [12] .

În 2003, Ed Pegg Jr. a scris într-un articol de pe site-ul web Mathematical Association of America că F24A merită un nume, dar nu a propus unul [13] . În cele din urmă, în 2007, David Epstein a folosit numele Earl of Nauru deoarece steagul Republicii Nauru conține o stea cu 12 colțuri, similară cu cea care apare atunci când graficul este construit ca un grafic Petersen generalizat. [unu]

Note

  1. ↑ 1 2 3 David Eppstein, The many faces of the Nauru graph Arhivat din original pe 21 iulie 2011. pe LiveJournal, 2007.
  2. ↑ 1 2 Conder, Dobcsányi, 2002 , p. 40, 41-63.
  3. ↑ Pegg, Exoo, 2009 .
  4. ^ Weisstein , Eric W. Graph Crossing Number  pe site- ul Wolfram MathWorld .
  5. ↑ Royle, G. Date F024A Arhivat 6 martie 2011 la Wayback Machine
  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. ↑ Zaharia, 1941 , p. 147–170.
  13. ^ Pegg , 2003 .

Literatură