Greve av Nauru

Greve av Nauru
Toppar 24
revben 36
Radie fyra
Diameter fyra
Omkrets 6
Automorfismer 144 ( S4 × S3 )
Kromatiskt nummer 2
Kromatiskt index 3
Egenskaper

kubisk
symmetrisk
Hamiltonsk
tvådelad
Cayley-graf


hela
 Mediafiler på Wikimedia Commons

I grafteorin är Nauru-grafen  en symmetrisk tvådelad kubisk graf med 24 hörn och 36 kanter. Jarlen döptes David Epstein efter den tolvuddiga stjärnan på Naurus flagga . [ett]

Grafens kromatiska nummer är 2, det kromatiska indexet är 3, diametern är 4, radien  är 4 och omkretsen är 6 [2] . Grafen är 3-vertex-ansluten och 3-kant-ansluten .

De minsta kubikgraferna med korsningar 1-8 är kända (sekvens A110507 i OEIS ). Den minsta grafen med 8 korsningar är Nauru-grafen. Det finns 5 icke-isomorfa kubiska grafer med 24 hörn och 8 skärningar [3] . En av dem är Count McGee , även känd som (3-7) -cell . [fyra]

Byggnad

Naurugrafen är Hamiltonsk och kan beskrivas med LCF-notation  : [5, −9, 7, −7, 9, −5] 4 . [ett]

Nauru-grafen kan också konstrueras som en generaliserad Petersen-graf G (12, 5) som bildas av hörnen på en dodekagon , där kanter förbinder hörnen för att bilda en 12-strålad stjärna genom att koppla hörnen med ett steg på 5.

En konstruktion baserad på kombinatorik är också möjlig . Låt oss ta tre olika föremål och lägga dem i fyra oskiljbara lådor, inte mer än ett föremål per låda. Det finns 24 sätt att placera objekt, vilket motsvarar 24 grafhörn. Om det är möjligt att flytta från en placering till en annan genom att flytta exakt ett föremål till en tom låda, kopplar vi två hörn med en kant. Den resulterande övergångsgrafen från plats till plats är Nauru-grafen.

Algebraiska egenskaper

Automorfismgruppen i Naurugrafen är en grupp av ordning 144. [5] . Gruppen är isomorf till den direkta produkten av de symmetriska grupperna S 4 och S 3 och verkar transitivt på grafens hörn, kanter och bågar. Således är Nauru-grafen symmetrisk (men inte avståndstransitiv ). Grafen har automorfismer som mappar vilken vertex som helst till vilken som helst annan och vilken kant som helst till vilken annan. Enligt Fosters lista är Nauru-grafen den enda kubiska symmetriska grafen med 24 hörn [2] .

En generaliserad Petersen-graf G ( n, k ) är vertextransitiv om och endast om n  = 10 och k  =2 eller om k 2  ≡ ±1 (mod  n ) och är kanttransitiv endast om: ( n, k ) = (4.1), (5.2), (8.3), (10.2), (10.3), (12.5), (24.5) [6] . Således är Nauru-grafen en av de sju symmetriska generaliserade Petersen-graferna. Dessa sju grafer inkluderar den kubiska grafen , Petersen -grafen , Möbius-Cantor-grafen , dodekaedergrafen och Desargues-grafen .

Nauru - grafen är Cayley-grafen för S 4 -gruppen, en symmetrisk permutationsgrupp med fyra element som bildas genom att permutera det första elementet med tre andra: (1 2), (1 3) och (1 4).

Det karakteristiska polynomet för Nauru-grafmatrisen är

därav följer att grafen är ett heltal — en  graf vars spektrum endast består av heltal.

Topologiska egenskaper

Nauru-grafen har två olika inbäddningar som en generaliserad regelbunden polyeder , där de topologiska ytorna är uppdelade i kanter, hörn och ytor på ett sådant sätt att det finns en symmetri som tar vilken flagga som helst (den infallande trippeln av en vertex, kant, och ansikte) till någon annan flagga [7] .

En av dessa två inbäddningar bildar en torus , så Nauru-grafen är en toroidform - den  består av 12 hexagonala ytor tillsammans med 24 hörn och 36 ytor Nauru-grafer. Den dubbla grafen för denna inbäddning är en symmetrisk 6-regelbunden graf med 12 hörn och 36 kanter.

En annan symmetrisk inbäddning av Nauru-grafen har sex tvåsidiga ytor och bildar en yta av genus 4. Dess dubbla graf är inte en enkel graf , eftersom varje yta delar tre kanter med fyra andra ytor, utan är en multigraf . Denna dubbla graf kan bildas från grafen för en vanlig oktaeder genom att ersätta varje kant med tre parallella kanter.

Uppsättningen av ytor för någon av dessa två inbäddningar är uppsättningen av Petri-polygoner för den andra inbäddningen.

Geometriska egenskaper

Liksom alla generaliserade Petersen-grafer kan Nauru-grafen representeras som punkter i planet på ett sådant sätt att intilliggande hörn är på ett avstånd av ett. Det är alltså en enhetsdistansgraf [8] . Denna graf och prismat är de enda generaliserade Petersen-graferna G ( n , p ) som inte kan representeras på ett sådant sätt att symmetrierna i mönstret bildar en cyklisk grupp av ordningen n . Istället har dess grafrepresentation den dihedriska gruppen Dih 6 som sin symmetrigrupp .

Historik

Den första personen som skrev om Naurus graf var Foster, som listade grafen i listan över alla kubiska symmetriska grafer [9] . En komplett lista med kubiska symmetriska grafer är nu uppkallad efter honom ( Foster's List ) och i denna lista är räkningen av Nauru numrerad F24A men får inget namn [10] . År 1950 nämnde Coxeter grafen för andra gången och gav en Hamiltonsk representation för att illustrera papperet och beskrev grafen som en Levi-graf av den projektiva konfigurationen upptäckt av Zaharias [11] [12] .

2003 skrev Ed Pegg Jr i en artikel på Mathematical Association of Americas webbplats att F24A förtjänade ett namn, men föreslog inte ett [13] . Slutligen, 2007, använde David Epstein namnet Earl of Nauru eftersom Republiken Naurus flagga innehåller en 12-uddig stjärna, liknande den som uppstår när grafen är konstruerad som en generaliserad Petersen-graf. [ett]

Anteckningar

  1. ↑ 1 2 3 David Eppstein, Naurugrafens många ansikten Arkiverad från originalet den 21 juli 2011. på LiveJournal, 2007.
  2. ↑ 1 2 Conder, Dobcsányi, 2002 , sid. 40, 41-63.
  3. ↑ Pegg, Exoo, 2009 .
  4. ↑ Weisstein, Eric W. Graph Crossing Number  på Wolfram MathWorld- webbplatsen .
  5. ↑ Royle, G. F024A-data Arkiverad 6 mars 2011 på Wayback Machine
  6. ↑ Frucht, Graver, Watkins, 1971 , sid. 211–218.
  7. ↑ McMullen, 1992 , sid. 285–289.
  8. ↑ 1 2 Zitnik, Horvat, Pisanski, 2010 .
  9. ↑ Foster, 1932 , sid. 309–317.
  10. ↑ Bouwer, Chernoff, Monson, Star, 1988 .
  11. ↑ Coxeter, 1950 , sid. 413–455.
  12. ↑ Zacharias, 1941 , sid. 147–170.
  13. ↑ Pegg, 2003 .

Litteratur