Yleistetty Petersen-graafi

Graafiteoriassa yleistetty Petersen - graafi on kuutiograafien perhe, joka on muodostettu yhdistämällä säännöllisen monikulmion kärjet tähden vastaaviin pisteisiin . Perhe sisältää Petersen-graafin ja yleistää yhden Petersen-graafin rakentamistavan. Yleistettyjen Petersen-graafien perheen esitteli vuonna 1950 Coxeter [1] ja Mark Watkins [2] nimesi nämä graafit vuonna 1969 .

Määritelmä ja nimitys

Watkinsin merkinnöissä G ( n , k ) on kärkijoukon graafi

{ u 0 , u 1 , ..., u n −1 , v 0 , v 1 , ..., v n −1 }

ja monia kylkiluita

{ u i u i +1 , u i v i , v i v i + k : i  = 0,..., n  − 1}

jossa indeksit otetaan modulo n ja k < n /2. Saman graafin Coxeterin merkintä olisi { n }+{ n/k }, yhdistelmä säännöllisen n - kulman Schläfli-symbolista ja tähdestä , josta graafi muodostetaan. Mikä tahansa yleistetty Petersen-graafi voidaan rakentaa jännitysgraafiksi graafista, jossa on kaksi kärkeä, kaksi silmukkaa ja yksi reuna [3] .

Itse Petersen-graafi on G (5,2) tai {5}+{5/2}.

Esimerkkejä

Yleistettyjen Petersen-graafien joukossa ovat n - prisma G ( n ,1), Dürer-graafi G (6,2), Möbius-Cantor-graafi G (8,3), dodekaedri G (10,2), Desargues. graafi G (10,3 ) ja Count Nauru G (12,5).

Neljä yleistettyä Petersen-graafia, kolmioprisma, 5-kulmainen prisma, Dürer-graafi ja G (7,2), ovat seitsemässä graafissa, jotka ovat kuutioisia , 3-kärkiliitoksia ja hyvin peitettyjä (eli kaikki sen suurimmista itsenäisistä joukoista on yksi ja sama koko) [4] .

Ominaisuudet

Tällä kaavioperheellä on useita mielenkiintoisia ominaisuuksia. Esimerkiksi:

  1. G ( n , k ) on kärkitransitiivinen (eli on olemassa symmetrioita, jotka vievät minkä tahansa kärjen mihin tahansa toiseen) jos ja vain jos n  = 10 ja k  = 2 tai jos k 2  ≡ ±1 (mod  n ).
  2. Se on reunatransitiivinen (jossa on symmetriaa, joka kuvaa minkä tahansa reunan mihin tahansa muuhun) vain seuraavissa seitsemässä tapauksessa: ( n , k ) = (4.1), (5.2), (8.3), (10.2), (10.3), ( 12.5), (24.5) [5] . Vain nämä seitsemän kuvaajaa ovat symmetrisiä yleistettyjä Petersen-graafia.
  3. Se on kaksiosainen silloin ja vain, jos n on parillinen ja k on pariton.
  4. Se on Cayley-graafi , jos ja vain jos k 2  ≡ 1 (mod  n ).
  5. Se on hypo -Hamiltonin , jos n on kongruentti 5:n modulo 6:n kanssa ja k on yhtä suuri kuin 2, n − 2, ( n + 1)/2 tai ( n − 1)/2 (kaikki neljä näistä k -arvoista johtavat isomorfisiin kaavioihin). Se ei ole Hamiltonin , jos n on jaollinen neljällä, ainakin kun arvo on 8, ja k on yhtä kuin n /2. Kaikissa muissa tapauksissa sillä on Hamiltonin sykli [6] . Jos n on kongruentti 3:n moduulin 6 kanssa ja k on 2, G ( n , k ) on täsmälleen kolme Hamiltonin sykliä [7] , G ( n ,2) Hamiltonin syklien lukumäärä voidaan laskea luokista riippuen kaavalla n: stä modulo kuusi , ja se sisältää Fibonacci-luvut [8] .

Petersen-graafi on ainoa yleistetty Petersen-graafi, jota ei voida värjätä reunavärillä kolmella värillä [9] . Yleistetty Petersen-graafi G (9,2) on yksi harvoista tunnetuista graafista, jota ei voida värjätä reunavärillä kolmella värillä [10] .

Mikä tahansa yleistetty Petersen -graafi on yksikköetäisyysgraafi [11] .

Muistiinpanot

  1. ↑ HSM Coxeter. Itsenäiset kaksoiskokoonpanot ja säännölliset kaaviot // Bulletin of the American Mathematical Society . - 1950. - T. 56 . - S. 413-455 . - doi : 10.1090/S0002-9904-1950-09407-5 .
  2. ↑ Mark E. Watkins. Lause hännän värjäyksistä yleistettyjen Petersen-graafien sovelluksella // Journal of Combinatorial Theory . - 1969. - T. 6 . - S. 152-164 . - doi : 10.1016/S0021-9800(69)80116-X .
  3. ↑ Jonathan L. Gross, Thomas W. Tucker. Esimerkki 2.1.2. // Topologinen graafiteoria . - New York: Wiley, 1987. - s  . 58 .
  4. ↑ S. R. Campbell, M. N. Ellingham, Gordon F. Royle. Hyvin peitettyjen kuutiokaavioiden luonnehdinta // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1993. - T. 13 . - S. 193-212 .
  5. ↑ R. Frucht, J.E. Graver, M.E. Watkins. Yleistetyn Graf Petersenin ryhmät // Proceedings of the Cambridge Philosophical Society . - 1971. - T. 70 . - S. 211-218 . - doi : 10.1017/S0305004100049811 .
  6. ↑ B. R. Alspach. Hamiltonin yleistettyjen Petersen-graafien luokittelu // Journal of Combinatorial Theory, sarja B. - 1983. - V. 34 . - S. 293-312 . - doi : 10.1016/0095-8956(83)90042-4 .
  7. ↑ Andrew Thomason. Kuutiograafit, joissa on kolme Hamiltonin sykliä, eivät aina ole yksiselitteisesti väritettäviä reunalla  // Journal of Graph Theory. - 1982. - T. 6 , no. 2 . - S. 219-221 . - doi : 10.1002/jgt.3190060218 .
  8. ↑ Allen J. Schwenk. Hamiltonin syklien luettelointi tietyissä yleistetyissä Petersen-kaavioissa // Journal of Combinatorial Theory . - 1989. - T. 47 . - S. 53-59 . - doi : 10.1016/0095-8956(89)90064-6 .
  9. ↑ Frank Castagna, Geert Prins. Jokaisessa yleistetyssä Petersen-kaaviossa on Tait Coloring // Pacific Journal of Mathematics . - 1972. - T. 40 .
  10. ↑ Bela Bollobas. Extreme Graph Theory. - Dover, 2004. - s. 233. Vuoden 1978 Academic Pressin uusintapainos
  11. ↑ Arjana Žitnik, Boris Horvat, Tomaž Pisanski. Kaikki yleistetut Petersen-graafit ovat yksikköetäisyyskaavioita. - 2010. - T. 1109 .