Generaliserad Petersen-graf

I grafteorin är en generaliserad Petersen -graf en familj av kubiska grafer som bildas genom att förbinda hörn av en vanlig polygon med motsvarande hörn av en stjärna . Familjen inkluderar Petersen-grafen och generaliserar ett av sätten att konstruera Petersen-grafen. Familjen av generaliserade Petersen-grafer introducerades 1950 av Coxeter [1] och dessa grafer namngavs 1969 av Mark Watkins [2] .

Definition och beteckning

I Watkins notation är G ( n , k ) en vertexuppsättningsgraf

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

och många revben

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

där indexen tas modulo n och k < n /2. Coxeter-notationen för samma graf skulle vara { n }+{ n/k }, en kombination av Schläfli-symbolen för en vanlig n - gon och stjärnan från vilken grafen är bildad. Vilken generaliserad Petersen-graf som helst kan konstrueras som en stressgraf från en graf med två hörn, två slingor och ytterligare en kant [3] .

Själva Petersen-grafen är G (5,2) eller {5}+{5/2}.

Exempel

Bland de generaliserade Petersen-graferna finns n -prisma G ( n ,1), Dürer-grafen G (6,2), Möbius-Cantor-grafen G (8,3), dodekaedern G (10,2), Desargues graf G (10,3 ) och Count Nauru G (12,5).

De fyra generaliserade Petersen-graferna, det triangulära prismat, det 5-gonala prismat, Dürer-grafen och G (7,2), finns i sju grafer som är kubiska , 3-vertex-anslutna och vältäckta (vilket betyder att alla av dess största oberoende uppsättningar har en och samma storlek) [4] .

Egenskaper

Denna familj av grafer har ett antal intressanta egenskaper. Till exempel:

  1. G ( n , k ) är vertextransitiv (vilket betyder att det finns symmetrier som tar vilken vertex som helst till någon annan) om och endast om n  = 10 och k  =2 eller om k 2  ≡ ±1 (mod  n ).
  2. Den är kanttransitiv (har symmetrier som mappar vilken kant som helst till vilken som helst) endast i följande sju fall: ( n , k ) = (4.1), (5.2), (8.3), (10.2), (10.3), ( 12,5), (24,5) [5] . Endast dessa sju grafer är symmetriska generaliserade Petersen-grafer.
  3. Det är tvådelat om och endast om n är jämnt och k är udda.
  4. Det är en Cayley-graf om och endast om k 2  ≡ 1 (mod  n ).
  5. Det är hypo -Hamiltonskt om n är kongruent med 5 modulo 6 och k är lika med 2, n − 2, ( n + 1)/2 eller ( n − 1)/2 (alla dessa fyra k- värden leder till isomorfa grafer). Det är inte Hamiltonskt om n är delbart med fyra, åtminstone när värdet är 8, och k är lika med n /2. I alla andra fall har den en Hamiltonsk cykel [6] . Om n är kongruent med 3 modulo 6 och k är 2, har G ( n , k ) exakt tre Hamiltoncykler [7] , för G ( n ,2) kan antalet Hamiltoncykler beräknas med en formel beroende på klasserna av n modulo six , och involverar Fibonacci-nummer [8] .

Petersen-grafen är den enda generaliserade Petersen-grafen som inte kan kantfärgas med 3 färger [9] . Den generaliserade Petersen-grafen G (9,2) är en av få kända grafer som inte kan kantfärgas med 3 färger [10] .

Varje generaliserad Petersen -graf är en enhetsdistansgraf [11] .

Anteckningar

  1. ↑ HSM Coxeter. Självdubbla konfigurationer och vanliga grafer // Bulletin of the American Mathematical Society . - 1950. - T. 56 . - S. 413-455 . - doi : 10.1090/S0002-9904-1950-09407-5 .
  2. ↑ Mark E. Watkins. A Theorem on Tait Colorings with a Application to the generalized Petersen graphs // 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. Exempel 2.1.2. // Topologisk grafteori . - New York: Wiley, 1987. - S.  58 .
  4. ↑ S. R. Campbell, M. N. Ellingham, Gordon F. Royle. En karaktärisering av vältäckta kubikgrafer // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1993. - T. 13 . - S. 193-212 .
  5. ↑ R. Frucht, J.E. Graver, M.E. Watkins. Grupperna av den generaliserade Graf Petersen // Proceedings of the Cambridge Philosophical Society . - 1971. - T. 70 . - S. 211-218 . - doi : 10.1017/S0305004100049811 .
  6. ↑ B. R. Alspach. Klassificeringen av Hamiltonian generaliserade Petersen-grafer // Journal of Combinatorial Theory, Series B. - 1983. - V. 34 . - S. 293-312 . - doi : 10.1016/0095-8956(83)90042-4 .
  7. ↑ Andrew Thomason. Kubikgrafer med tre Hamiltonska cykler är inte alltid unikt kantfärgbara  // Journal of Graph Theory. - 1982. - T. 6 , nr. 2 . - S. 219-221 . - doi : 10.1002/jgt.3190060218 .
  8. ↑ Allen J. Schwenk. Uppräkning av Hamiltons cykler i vissa generaliserade Petersen-grafer // Journal of Combinatorial Theory . - 1989. - T. 47 . - S. 53-59 . - doi : 10.1016/0095-8956(89)90064-6 .
  9. ↑ Frank Castagna, Geert Prins. Varje generaliserad Petersen-graf har en Tait Coloring // Pacific Journal of Mathematics . - 1972. - T. 40 .
  10. ↑ Bela Bollobas. Extrem grafteori. - Dover, 2004. - s. 233. Reprint edition of 1978 Academic Press
  11. ↑ Arjana Žitnik, Boris Horvat, Tomaž Pisanski. Alla generaliserade Petersen-grafer är grafer för enhetsavstånd. - 2010. - T. 1109 .