Általánosított Petersen-gráf

A gráfelméletben az általánosított Petersen -gráf köbös gráfok családja, amelyet egy szabályos sokszög csúcsainak a csillag megfelelő csúcsaival való összekapcsolásával alakítanak ki . A család magában foglalja a Petersen-gráfot , és általánosítja a Petersen-gráf felépítésének egyik módját. Az általánosított Petersen-gráfok családját 1950-ben Coxeter vezette be [1] , és ezeket a gráfokat 1969-ben Mark Watkins [2] nevezte el .

Meghatározás és megnevezés

A Watkins-jelölésben G ( n , k ) egy csúcskészletű gráf

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

és sok borda

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

ahol az indexeket modulo n és k < n /2. Ugyanennek a gráfnak a Coxeter-jelölése a következő lenne: { n }+{ n/k }, a szabályos n - szög Schläfli-szimbólumának és a gráfot alkotó csillagnak a kombinációja. Bármely általánosított Petersen-gráf megszerkeszthető feszültséggráfként egy két csúcsú, két hurokkal és még egy éllel rendelkező gráfból [3] .

Maga a Petersen-gráf G (5,2) vagy {5}+{5/2}.

Példák

Az általánosított Petersen-gráfok közül az n -prizma G ( n ,1), a Dürer-gráf G (6,2), a Möbius-Cantor-gráf G (8,3), a dodekaéder G (10,2), a Desargues . G grafikon (10,3 ) és Nauru G grófja (12,5).

A négy általánosított Petersen-gráf, a háromszög-prizma, az 5-szögű prizma, a Dürer-gráf és a G (7,2) hét gráfban található, amelyek köbös , 3-csúcsos összeköttetésűek és jól fedettek (ami azt jelenti, hogy az összes legnagyobb független halmazainak egy és azonos méretű) [4] .

Tulajdonságok

Ez a grafikoncsalád számos érdekes tulajdonsággal rendelkezik. Például:

  1. G ( n , k ) csúcstranzitív (azaz vannak olyan szimmetriák, amelyek bármelyik csúcsot felveszik bármely másik csúcsra), akkor és csak akkor, ha n  = 10 és k  = 2, vagy ha k 2  ≡ ±1 (mod  n ).
  2. Éltranzitív (olyan szimmetriája van, amely bármely élre leképez) csak a következő hét esetben: ( n , k ) = (4.1), (5.2), (8.3), (10.2), (10.3), ( 12.5), (24.5) [5] . Csak ez a hét gráf szimmetrikus általánosított Petersen-gráf.
  3. Akkor és csak akkor kétrészes , ha n páros és k páratlan.
  4. Ez egy Cayley-gráf akkor és csak akkor, ha k 2  ≡ 1 (mod  n ).
  5. Hipo- Hamilton , ha n kongruens 5 modulo 6-tal, és k egyenlő 2, n - 2, ( n + 1)/2 vagy ( n - 1)/2 (mind a négy k érték vezet izomorf gráfokhoz). Nem Hamilton -féle , ha n osztható néggyel, legalább akkor, ha az érték 8, és k egyenlő n /2-vel. Minden más esetben Hamilton-ciklusa van [6] . Ha n kongruens 3 modulo 6-val és k 2, G ( n , k ) pontosan három Hamilton-ciklussal rendelkezik [7] , G ( n ,2) esetén a Hamilton-ciklusok száma az osztályoktól függő képlettel kiszámítható. n modulo six , és Fibonacci számokat tartalmaz [8] .

A Petersen-gráf az egyetlen olyan általánosított Petersen-gráf, amelyet nem lehet 3 színnel élszínezni [9] . Az általánosított Petersen-gráf G (9,2) azon kevés ismert gráfok egyike, amely nem színezhető 3 színnel élre [10] .

Bármely általánosított Petersen -gráf egységnyi távolsággráf [11] .

Jegyzetek

  1. ↑ HSM Coxeter. Önkettős konfigurációk és szabályos gráfok // Bulletin of the American Mathematical Society . - 1950. - T. 56 . - S. 413-455 . - doi : 10.1090/S0002-9904-1950-09407-5 .
  2. ↑ Mark E. Watkins. Tétel a farokszínezésről az általánosított Petersen-gráfokra való alkalmazással // 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. Példa 2.1.2. // Topológiai gráfelmélet . - New York: Wiley, 1987. -  58. o .
  4. ↑ S. R. Campbell, M. N. Ellingham, Gordon F. Royle. A jól lefedett köbös gráfok jellemzése // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1993. - T. 13 . - S. 193-212 .
  5. ↑ R. Frucht, J. E. Graver, M. E. Watkins. Az általánosított Graf Petersen csoportjai // Proceedings of the Cambridge Philosophical Society . - 1971. - T. 70 . - S. 211-218 . - doi : 10.1017/S0305004100049811 .
  6. ↑ B. R. Alspach. A Hamiltoni általánosított Petersen-gráfok osztályozása // Journal of Combinatorial Theory, B. sorozat - 1983. - V. 34 . - S. 293-312 . - doi : 10.1016/0095-8956(83)90042-4 .
  7. ↑ Andrew Thomason. A három Hamilton-ciklusú köbös gráfok nem mindig egyedileg színezhetők élekkel  // Journal of Graph Theory. - 1982. - T. 6 , sz. 2 . - S. 219-221 . - doi : 10.1002/jgt.3190060218 .
  8. ↑ Allen J. Schwenk. Hamilton-ciklusok felsorolása bizonyos általánosított Petersen-gráfokban // Journal of Combinatorial Theory . - 1989. - T. 47 . - S. 53-59 . - doi : 10.1016/0095-8956(89)90064-6 .
  9. ↑ Frank Castagna, Geert Prins. Minden általánosított Petersen-gráfhoz tartozik Tait Coloring // Pacific Journal of Mathematics . - 1972. - T. 40 .
  10. ↑ Bollobas Béla. Extrém gráfelmélet. - Dover, 2004. - 233. o. Az Academic Press 1978-as reprint kiadása
  11. ↑ Arjana Žitnik, Boris Horvat, Tomaž Pisanski. Minden általánosított Petersen-gráf egységnyi távolságú gráf. - 2010. - T. 1109 .