Naurun kreivi

Graafiteoriassa Nauru-graafi on  symmetrinen kaksiosainen kuutiograafi , jossa on 24 kärkeä ja 36 reunaa. David Epstein antoi jaarille nimen lipussa olevan 12-sakaraisen tähden mukaan . [yksi]

Graafin kromaattinen luku on 2, kromaattinen indeksi 3, halkaisija 4, säde  4 ja ympärysmitta 6 [2] . Kaavio on yhdistetty 3 kärkipisteeseen ja 3 reunaan yhdistetty .

Pienimmät kuutiograafit risteyksillä 1-8 tunnetaan (sekvenssi A110507 OEIS : ssä ). Pienin kaavio, jossa on 8 risteystä, on Nauru-graafi. On 5 ei-isomorfista kuutiograafia, joissa on 24 kärkeä ja 8 leikkauspistettä [3] . Yksi niistä on Count McGee , joka tunnetaan myös nimellä (3-7) -solu . [neljä]

Rakentaminen

Nauru-graafi on Hamiltonin ja sitä voidaan kuvata käyttämällä LCF-merkintää  : [5, −9, 7, −7, 9, −5] 4 . [yksi]

Nauru-graafi voidaan rakentaa myös yleistettynä Petersen-graafina G (12, 5), jonka muodostavat kaksikymmentäkolman kärjet , jossa reunat yhdistävät kärjet muodostaen 12-säteen tähden yhdistämällä kärjet askeleella 5.

Myös kombinatoriikkaan perustuva konstruktio on mahdollinen . Otetaan kolme erilaista esinettä ja laitetaan ne neljään erottamattomaan laatikkoon, enintään yksi esine per laatikko. Objektien sijoittamiseen on 24 tapaa, mikä vastaa 24 graafin kärkeä. Jos on mahdollista siirtyä paikasta toiseen siirtämällä täsmälleen yksi kohde tyhjään laatikkoon, yhdistämme kaksi kärkeä reunalla. Tuloksena oleva sijainnista sijaintiin siirtymäkaavio on Nauru-graafi.

Algebralliset ominaisuudet

Nauru-graafin automorfismiryhmä on luokkaa 144 oleva ryhmä. [5] . Ryhmä on isomorfinen symmetristen ryhmien S 4 ja S 3 suoralle tulolle ja vaikuttaa transitiivisesti graafin kärkipisteisiin, reunoihin ja kaareihin. Siten Nauru-graafi on symmetrinen (vaikkakaan ei etäisyystransitiivinen ). Graafilla on automorfismit, jotka kuvaavat minkä tahansa kärjen mihin tahansa toiseen ja minkä tahansa reunan mihin tahansa muuhun. Fosterin listan mukaan Nauru-graafi on ainoa kuutiosymmetrinen graafi, jossa on 24 kärkeä [2] .

Yleistetty Petersen-graafi G ( n, k ) on kärkitransitiivinen silloin ja vain jos n  = 10 ja k  =2 tai jos k 2  ≡ ±1 (mod  n ) ja on reunatransitiivinen vain jos: ( n, k ) = (4.1), (5.2), (8.3), (10.2), (10.3), (12.5), (24.5) [6] . Siten Nauru-graafi on yksi seitsemästä symmetrisestä yleistetystä Petersen-graafista. Nämä seitsemän kuvaajaa sisältävät kuutiograafin , Petersenin graafin , Möbius-Cantorin graafin , dodekaedrigraafin ja Desarguesin graafin .

Nauru -graafi on S 4 -ryhmän Cayley-graafi , symmetrinen neljän elementin permutaatioryhmä, joka muodostetaan permutoimalla ensimmäinen elementti kolmen muun kanssa: (1 2), (1 3) ja (1 4).

Nauru-graafimatriisin ominaispolynomi on

mistä seuraa, että graafi on kokonaisluku —  graafi, jonka spektri koostuu vain kokonaisluvuista.

Topologiset ominaisuudet

Nauru-graafissa on kaksi erilaista upotusta yleistettynä säännöllisenä monitahoisena , jossa topologiset pinnat on jaettu reunoihin, kärkipisteisiin ja pintoihin siten, että on symmetria, joka ottaa minkä tahansa lipun (pisteen sattuva kolmio, reuna, ja kasvot) mihin tahansa muuhun lippuun [7] .

Toinen näistä kahdesta upotuksesta muodostaa toruksen , joten Nauru-graafi on toroidinen graafi – se  koostuu 12 kuusikulmaisesta pinnasta sekä 24 pisteestä ja 36 pinnasta Nauru-graafista. Tämän upotuksen kaksoisgraafi on symmetrinen 6-säännöllinen graafi, jossa on 12 kärkeä ja 36 reunaa.

Toisessa Nauru-graafin symmetrisessä upotuksessa on kuusi kaksikulmaista pintaa ja se muodostaa pinnan suku 4. Sen kaksoisgraafi ei ole yksinkertainen graafi , koska jokaisella pinnalla on kolme reunaa neljän muun pinnan kanssa, vaan se on multigrafi . Tämä kaksoisgraafi voidaan muodostaa säännöllisen oktaedrin graafista korvaamalla jokainen reuna kolmella yhdensuuntaisella reunalla.

Jommankumman upotuksen pintojen joukko on toisen upotuksen Petri-polygonien joukko .

Geometriset ominaisuudet

Kuten kaikki yleistetut Petersen-graafit, Nauru-graafi voidaan esittää tason pisteinä siten, että vierekkäiset kärjet ovat yhden etäisyydellä. Siten se on yksikköetäisyysgraafi [8] . Tämä graafi ja prisma ovat ainoat yleistetyt Petersenin graafit G ( n , p ) , joita ei voida esittää siten , että kuvion symmetriat muodostavat kertaluvun n syklisen ryhmän . Sen sijaan sen graafiesityksen symmetriaryhmänä on dihedraaliryhmä Dih 6 .

Historia

Ensimmäinen henkilö, joka kirjoitti Naurun graafista, oli Foster, joka listasi graafin kaikkien kuutiosymmetristen graafien luetteloon [9] . Täydellinen luettelo kuutiosymmetrisistä kaavioista on nyt nimetty hänen mukaansa ( Foster's List ), ja tässä luettelossa Naurun määrä on numeroitu F24A, mutta sille ei ole annettu mitään nimeä [10] . Vuonna 1950 Coxeter mainitsi graafin toisen kerran, antaen Hamiltonin esityksen paperin havainnollistamiseksi ja kuvailemalla kuvaajaa Zahariasin löytämän projektiivisen konfiguraation Levi -graafina [11] [12] .

Vuonna 2003 Ed Pegg Jr. kirjoitti artikkelissa Mathematical Association of America -verkkosivustolla , että F24A ansaitsi nimen, mutta ei ehdottanut sitä [13] . Lopuksi, vuonna 2007, David Epstein käytti nimeä Earl of Naurun, koska Naurun tasavallan lippu sisältää 12-sakaraisen tähden, joka on samanlainen kuin se, joka esiintyy, kun kaavio rakennetaan yleistetyksi Petersen-graafiksi. [yksi]

Muistiinpanot

1. ↑ 1 2 3 David Eppstein, Nauru-graafin monet kasvot Arkistoitu alkuperäisestä 21. heinäkuuta 2011. LiveJournalissa 2007.
2. ↑ 1 2 Conder, Dobcsányi, 2002 , s. 40, 41-63.
3. ↑ Pegg, Exoo, 2009 .
4. ↑ Weisstein, Eric W. Graph Crossing Number  Wolfram MathWorld -verkkosivustolla .
5. ↑ Royle, G. F024A-tiedot Arkistoitu 6. maaliskuuta 2011 Wayback Machinessa
6. ↑ Frucht, Graver, Watkins, 1971 , s. 211–218.
7. ↑ McMullen, 1992 , s. 285–289.
8. ↑ 1 2 Zitnik, Horvat, Pisanski, 2010 .
9. ↑ Foster, 1932 , s. 309-317.
10. ↑ Bouwer, Chernoff, Monson, Star, 1988 .
11. ↑ Coxeter, 1950 , s. 413–455.
12. ↑ Sakarias, 1941 , s. 147-170.
13. ↑ Pegg, 2003 .

Kirjallisuus

• M. Conder, P. Dobcsany. Kolmiarvoiset symmetriset kuvaajat jopa 768 kärkeä. // J. Combin. Matematiikka. Yhdistää. Laske... - 2002.
• ET Pegg, G. Exoo. Crossing number graphs // Mathematica Journal. - 2009. - T. 11 .
• R. Frucht, J. E. Graver, M. E. Watkins. Yleistettyjen Petersen-graafien ryhmät // Proceedings of the Cambridge Philosophical Society . - 1971. - T. 70 . - doi : 10.1017/S0305004100049811 .
• Peter McMullen. Tyypin { p , 3} säännöllinen polyhedra, jossa on 2 p - pistettä // Geometriae Dedicata . - 1992. - T. 43 , no. 3 . - doi : 10.1007/BF00151518 .
• Arjana Žitnik, Boris Horvat, Tomaž Pisanski. Kaikki yleistetut Petersen-graafit ovat yksikköetäisyyskaavioita. - 2010. - T. 1109. - (IMFM preprints).
• RM Foster. Sähköverkkojen geometriset piirit // Transactions of the American Institute of Electrical Engineers . - 1932. - T. 51 . - doi : 10.1109/T-AIEE.1932.5056068 .
• IZ Bouwer, W. W. Chernoff, B. Monson, Z. Star. Foster Census. — Charles Babbage Research Centre, 1988.
• HSM Coxeter. Itsenäiset kaksoiskokoonpanot ja säännölliset kaaviot // Bulletin of the American Mathematical Society. - 1950. - T. 56 . - doi : 10.1090/S0002-9904-1950-09407-5 .
• M. Zacharias. Untersuchungen über ebene Konfigurationen (124, 163) // Deutsche Mathematik. - 1941. - T. 6 .
• Ed Pegg Jr. Kuutiosymmetriset kaaviot. - Mathematical Association of America, 2003.