Generaliseret Petersen graf

I grafteori er en generaliseret Petersen -graf en familie af kubiske grafer dannet ved at forbinde hjørnerne af en regulær polygon med de tilsvarende hjørner af en stjerne . Familien inkluderer Petersen-grafen og generaliserer en af ​​måderne at konstruere Petersen-grafen på. Familien af ​​generaliserede Petersen-grafer blev introduceret i 1950 af Coxeter [1] og disse grafer blev navngivet i 1969 af Mark Watkins [2] .

Definition og betegnelse

I Watkins notation er G ( n , k ) en vertex-set graf

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

og mange ribben

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

hvor indeksene er taget modulo n og k < n /2. Coxeter-notationen for den samme graf ville være { n }+{ n/k }, en kombination af Schläfli-symbolet for en regulær n - gon og stjernen , som grafen er dannet af. Enhver generaliseret Petersen-graf kan konstrueres som en stressgraf ud fra en graf med to spidser, to løkker og en kant mere [3] .

Selve Petersen-grafen er G (5,2) eller {5}+{5/2}.

Eksempler

Blandt de generaliserede Petersen-grafer er n -prisme G ( n ,1), Dürer-grafen G (6,2), Möbius-Cantor-grafen G (8,3), dodekaederet G (10,2), Desargues graf G (10,3 ) og Count Nauru G (12,5).

De fire generaliserede Petersen-grafer, det trekantede prisme, det 5-gonale prisme, Dürer-grafen og G (7,2), er i syv grafer, der er kubiske , 3-vertex-forbundne og godt dækkede (hvilket betyder, at alle af dets største uafhængige sæt har en og samme størrelse) [4] .

Egenskaber

Denne familie af grafer har en række interessante egenskaber. For eksempel:

  1. G ( n , k ) er toppunkttransitiv (hvilket betyder, at der er symmetrier, der tager et hvilket som helst toppunkt til et hvilket som helst andet), hvis og kun hvis n  = 10 og k  =2 eller hvis k 2  ≡ ±1 (mod  n ).
  2. Det er kanttransitivt (har symmetrier, der kortlægger enhver kant til enhver anden) kun i følgende syv tilfælde: ( n , k ) = (4.1), (5.2), (8.3), (10.2), (10.3), ( 12,5), (24,5) [5] . Kun disse syv grafer er symmetriske generaliserede Petersen-grafer.
  3. Den er todelt , hvis og kun hvis n er lige og k er ulige.
  4. Det er en Cayley-graf, hvis og kun hvis k 2  ≡ 1 (mod  n ).
  5. Det er hypo -Hamiltonsk, hvis n er kongruent med 5 modulo 6 og k er lig med 2, n − 2, ( n + 1)/2 eller ( n − 1)/2 (alle fire af disse k -værdier fører til isomorfe grafer). Det er ikke Hamiltonsk , hvis n er delelig med fire, i det mindste når værdien er 8, og k er lig med n /2. I alle andre tilfælde har den en Hamiltonsk cyklus [6] . Hvis n er kongruent med 3 modulo 6 og k er 2, har G ( n , k ) præcis tre Hamiltonske cyklusser [7] , for G ( n ,2) kan antallet af Hamiltonske cyklusser beregnes ved hjælp af en formel afhængig af klasserne af n modulo six , og involverer Fibonacci-tal [8] .

Petersen-grafen er den eneste generaliserede Petersen-graf, der ikke kan kantfarves med 3 farver [9] . Den generaliserede Petersen-graf G (9,2) er en af ​​de få kendte grafer, der ikke kan kantfarves med 3 farver [10] .

Enhver generaliseret Petersen -graf er en enhedsafstandsgraf [11] .

Noter

  1. ↑ HSM Coxeter. Selvdobbelte konfigurationer og regelmæssige 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 an 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. Eksempel 2.1.2. // Topologisk grafteori . - New York: Wiley, 1987. - S.  58 .
  4. ↑ S. R. Campbell, M. N. Ellingham, Gordon F. Royle. En karakterisering af godt dækkede kubiske grafer // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1993. - T. 13 . - S. 193-212 .
  5. ↑ R. Frucht, J.E. Graver, M.E. Watkins. Grupperne af den generaliserede Graf Petersen // Proceedings of the Cambridge Philosophical Society . - 1971. - T. 70 . - S. 211-218 . - doi : 10.1017/S0305004100049811 .
  6. ↑ B. R. Alspach. Klassifikationen af ​​Hamiltonske generaliserede 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. Kubiske grafer med tre Hamiltonske cyklusser er ikke altid entydigt kantfarvelige  // Journal of Graph Theory. - 1982. - T. 6 , no. 2 . - S. 219-221 . - doi : 10.1002/jgt.3190060218 .
  8. ↑ Allen J. Schwenk. Opregning af Hamiltonske cyklusser i visse generaliserede 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. Hver generaliseret Petersen-graf har en Tait Coloring // Pacific Journal of Mathematics . - 1972. - T. 40 .
  10. ↑ Bela Bollobas. Ekstrem grafteori. - Dover, 2004. - s. 233. Genoptrykt udgave af 1978 Academic Press
  11. ↑ Arjana Žitnik, Boris Horvat, Tomaž Pisanski. Alle generaliserede Petersen-grafer er enhedsafstandsgrafer. - 2010. - T. 1109 .