Nauru-graf

Nauru-graf
Representasjon av Nauru-grafen.

Vurdering	F24A
Antall hjørner	24
Antall kanter	36
Gradsfordeling	3- vanlig
Stråle	4
Diameter	4
Mesh	6
Automorfismer	144
Kromatisk nummer	2
Kromatisk indeks	3
Eiendommer	Vanlig Bipart Cubic Integral Hamiltonian Cayley

I matematikk , og mer presist i grafteori , er Nauru- grafen en 3-vanlig graf med 24 hjørner og 36 kanter. Den ble oppkalt av David Eppstein etter den 12-pekte stjernen som prydet Naurus flagg .

Eiendommer

Generelle egenskaper

Den diameteren av den Nauru grafen, er den maksimale eksentrisitet av dens topp-punkt, er 4, dens radius , den minimale eksentrisiteten av dens topp-punkt, er 4 og dens mesh , er lengden av den korteste syklus , er 6. Det er av et 3- toppunkt -tilkoblet graf og en 3 -kantstilkoblet graf , det vil si at den er tilkoblet og at for å gjøre den frakoblet må den fratas minst 3 hjørner eller 3 kanter.

Fargelegging

Det kromatiske tallet på Nauru-grafen er 2. Det vil si at det er mulig å fargelegge det med 2 farger slik at to hjørner forbundet med en kant alltid er forskjellige farger. Dette tallet er minimalt.

Den kromatiske indeksen til Nauru-grafen er 3. Det er derfor en trefarging av kantene på grafen slik at to kanter som faller inn i samme toppunkt alltid har forskjellige farger. Dette tallet er minimalt.

Algebraiske egenskaper

Nauru-grafen er symmetrisk , det vil si at dens gruppe av automorfismer virker transitt på kantene, toppunktene og buene. Det er derfor også kant-transitivt og toppunkt-transitivt . Nauru-grafen er den unike symmetriske kubiske grafen med 24 hjørner, og dens notasjon i Foster Census , katalogen som klassifiserer alle symmetriske kubiske grafer, er F24A.

Automorfisme-gruppen i Nauru-grafen er av orden 144. Den eksakte strukturen er kjent: den er isomorf til det direkte produktet av de symmetriske gruppene S 4 og S 3 .

Den generaliserte Petersen-grafen G ( n, k ) er toppunkt-transitiv hvis og bare hvis n = 10 og k = 2 eller hvis k 2 ≡ ± 1 (mod n ). Det er bare kantovergang i følgende syv tilfeller: ( n, k ) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5 ), (24,5). Så Nauru-grafen er en av de syv symmetriske generaliserte Petersen-grafene. De andre seks er den heksahedrale grafen , Petersen-grafen , Möbius-Kantor- grafen , den dodekedriske grafen og Desargues-grafen . ${\ displaystyle G (4,1)}$ ${\ displaystyle G (5,2)}$ ${\ displaystyle G (8,3)}$ ${\ displaystyle G (10,2)}$ ${\ displaystyle G (10.3)}$

Den karakteristiske polynom av naboskapsmatrisen nauru grafen er: . Det innrømmer bare hele røtter. Nauru-grafen er derfor en integrert graf , en graf hvis spektrum består av heltall. ${\ displaystyle (x-3) (x-2) ^ {6} (x-1) ^ {3} x ^ {4} (x + 1) ^ {3} (x + 2) ^ {6} ( x + 3)}$

Nauru-grafen har to forskjellige innebygninger som kan betraktes som generaliserte vanlige polyedre : overflater (eller mer presist todimensjonale manifolder ) spaltes i hjørner, kanter og ansikter, slik at det er en sammenheng (med respekt for forekomsten) av overflaten som sender noen flagg (en triplett dannet av et innfallende toppunkt, en kant og et ansikt) til ethvert annet flagg.

En av disse to innebygningene danner en torus, og Nauru-grafen er derfor en torisk graf : den er dannet av 12 sekskantede flater, og de 24 hjørner og 36 kanter av Nauru-grafen. Den doble grafen til denne innebyggingen er en symmetrisk 6-vanlig graf med 12 hjørner og 36 kanter.

Den andre symmetriske innebyggingen av Nauru-grafen har seks dodecagonale ansikter , og danner en overflate av slekt 4. Den doble er ikke en enkel graf , men en multigraf , siden hvert ansikt har tre sider til felles med fire andre ansikter. Denne doble grafen kan bygges fra en vanlig oktaeder ved å erstatte hver kant med en bunt med tre "parallelle" kanter.

Settet med ansikter til hver av disse to innblandingene er settet med Petrie-polygoner fra den andre innebyggingen.

Historie

Den første personen som publiserte på Nauru-grafen er RM Foster i et forsøk på å identifisere alle symmetriske kubiske grafer. Den komplette listen over symmetriske kubiske grafer ble kalt Foster Census etter ham. I denne listen har Nauru-grafen nummeret F24A, men har ikke et spesifikt navn. I 1950 siterte HSM Coxeter grafen for andre gang, og ga den Hamilton-representasjonen som ble brukt til å illustrere denne artikkelen og beskrev den som Levi-grafen over den prosjektive konfigurasjonen oppdaget av Zacharias.

I 2003 indikerer Ed Pegg i internettpublikasjonen til Mathematical Association of America at F24A fortjener et navn, men ikke tilbyr det. Til slutt, i 2007, David Eppstein heter det Nauru graf i referanse til flagget på Nauru som inneholder en tolv-spiss stjerne som ligner på det som vises i konstruksjonen av grafen som en generalisert Petersen graf .

Se også

Relaterte artikler

Grafteori

Referanser

(in) Eppstein, D. , De mange ansiktene til Nauru-grafen på LiveJournal, 2007.
(in) Conder, Dobcsányi M. og P. "Trivalente symmetriske grafer Opptil 768 hjørner." J. Combin. Matte. Kombiner. Beregn. 40, 41-63, 2002.
(in) Royle, G. "Cubic Symmetric Graphs (The Census Foster)" 2001.
(en) Royle, G. F024A data .
(in) R. Frucht , I Burn og E. Watkins , " The groups of the generalized Petersen graphs " , Proceedings of the Cambridge Philosophical Society , vol. 70, 1971, s. 211–218 ( DOI 10.1017 / S0305004100049811 ).
(in) Peter McMullen, The regular polyhedra of type { p , 3} with 2 p vertices , Geometriae Dedicata , vol.43 p. 285–289 (1992)
(in) RM Foster , " Geometrical circuits of elektriske nettverk ", Transactions of the American Institute of Electrical Engineers , vol. 51,1932, s. 309–317.
(i) IZ Bouwer , WW Chernoff , B. Monson og Z Star , " The Foster Census ," Charles Babbage Research Center ,1988.
(in) HSM Coxeter , " Selvdoble konfigurasjoner og vanlige grafer ", Bulletin of the American Mathematical Society , vol. 56,1950, s. 413-455.
(De) M. Zacharias , " Untersuchungen über ebene Konfigurationen (124, 163) ", Deutsche Mathematik , vol. 6,1941, s. 147–170.
(in) Ed Pegg , " Cubic Symmetric Graphs " , Mathematical Association of America , 2003( les online ).