Általánosított Petersen-gráf

matematikai fogalom a gráfelméletben

A matematika, azon belül a gráfelmélet területén egy általánosított Petersen-gráf (generalized Petersen graph) – jelölése GP(n,k), ahol n ≥ 3 és 1 ≤ k ≤ ⌊(n-1)/2⌋ – olyan összefüggő, 3-reguláris gráf, mely egy belső {n,k} csillagsokszög (cirkuláns gráf) és egy külső {n} szabályos sokszög (körgráf) megfelelő csúcsainak összekötésével állítható elő. Ha n és k nem relatív prímek, a csillagsokszög elfajult, nem összefüggő, de ettől még az általánosított Petersen-gráf megkonstruálható.

A Dürer-gráf, avagy GP(6,2).
A GP(12,4).

Az általánosított Petersen-gráfok családját 1950-ben H. S. M. Coxeter vezette be,[1] nevüket pedig 1969-ben Mark Watkinstól kapták.[2] A családba tartozik a Petersen-gráf is, melynek konstrukcióját általánosítják.

Definíció és jelölésekSzerkesztés

Watkins jelölése szerint G(n,k) egy olyan gráf, melynek csúcshalmaza

V(GP(n,k)): {u0, u1, ..., un−1, v0, v1, ..., vn−1},

élhalmaza pedig

E(GP(n,k)): {ui ui+1, ui vi, vi vi+k: i = 0,...,n − 1},

ahol az alsó indexek modulo n olvasandók és k < n/2. Más szerzők a GPG(n,k) vagy GP(n,k) jelölést alkalmazzák. Coxeter jelölésmódja ugyanerre a gráfra {n}+{n/k} lenne, a gráfot alkotó szabályos n-szög és csillagsokszög Schläfli-szimbólumainak kombinációjából. Bármely általánosított Petersen-gráf előállítható feszültséggráfként egy olyan gráfból, ami két csúcsból, a köztük lévő élből és két hurokélből áll.[3]

Maga a Petersen-gráf így jelölhető: GP(5,2) vagy {5}+{5/2}.

PéldákSzerkesztés

 
A GP(8,1) vagy 8-prizmagráf

Az általánosított Petersen-gráfok közé tartoznak a GP(n,1)-nel jelölt n-prizmagráfok, a GP(6,2) Dürer-gráf, a GP(8,3) Möbius–Kantor-gráf, a GP(10,2) dodekaéder, a GP(10,3) Desargues-gráf és a GP(12,5) Nauru-gráf is.

Az általánosított Petersen-gráfok közül négy – a 3-prizma, az 5-prizma, a Dürer-gráf és a GP(7,2) – beletartozik abba a hét különleges gráfba, melyekre igaz, hogy 3-regulárisak, 3-szorosan összefüggők és jól fedettek (azaz minden maximális független csúcshalmazuk azonos méretű).[4]

TulajdonságokSzerkesztés

 
A GP(9,2) három Hamilton-körének egyike. A másik két Hamilton-kör a lerajzolás 40°-os elforgatása szerint szimmetrikus.

Mivel az általánosított Petersen-gráfok 3-regulárisak, a GP(n,k) 2n csúccsal és 3n éllel rendelkezik.

Az általánosított Petersen-gráfok családjának további érdekes tulajdonságai vannak. Például

  1. GP(n,k) pontosan akkor csúcstranzitív (tehát van tetszőleges csúcsát másik csúcsba átvivő szimmetriája), ha n = 10 és k =2 vagy k2 ≡ ±1 (mod n).
  2. Kizárólag a következő hét esetben éltranzitív (tehát van tetszőleges élt másik élbe átvivő szimmetriája): (n,k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5).[5] Ezen a hét gráfon kívül tehát nem létezik szimmetrikus általánosított Petersen-gráf.
  3. Pontosan akkor páros, ha n páros, de k páratlan.
  4. Pontosan akkor Cayley-gráf, ha k2 ≡ 1 (mod n).
  5. Akkor hipohamiltoni, amikor n ≡ 5 (mod 6) és k értéke 2, n−2, (n+1)/2 vagy (n−1)/2 (ezek a k értékek izomorf gráfokhoz vezetnek). Akkor sincs Hamilton-kör bennük, ha n osztható néggyel, de legalább 8, és k = n/2. Minden más esetben van bennük Hamilton-kör.[6] Ha n ≡ 3 modulo 6 és k értéke 2, GP(n,k)-nak pontosan három Hamilton-köre van.[7] A GP(n,2) gráfok Hamilton-köreinek számát olyan képlet adja meg, ami egy n modulo 6 kongruenciaosztályon alapul és szerepelnek benne a Fibonacci-számok.[8]

Minden általánosított Petersen-gráf egyben egységtávolsággráf is.[9]

IzomorfizmusokSzerkesztés

GP(n,k) pontosan akkor izomorf GP(n,l)-lel, ha kl ≡ 1 (mod n).[10]

GirthparaméterSzerkesztés

Az általánosított Petersen-gráf girthparamétere, G(GP(n,k)) legalább 3 és legfeljebb 8 lehet, továbbá G(GP(n,k)) ≤  .[11]

Táblázat a pontos értékekkel:

Feltétel Girth
  3
  4
 
  5
 
 
  6
 
 
  7
 
 
 
 
 
Egyéb esetben 8

Kromatikus szám és élkromatikus számSzerkesztés

Reguláris gráfokról lévén szó, a Brooks-tétel értelmében a kromatikus szám legfeljebb a fokszámmal egyezhet meg. A 3-reguláris általánosított Petersen-gráfok esetében tehát a kromatikus szám 2 vagy 3 lehet. Pontosabban:

 

Ahol   a logikai ÉS,   pedig a logikai VAGY jelölése. Például a   esetén a kromatikus szám 3.

A Petersen-gráf, lévén snark, élkromatikus száma 4. Az összes többi általánosított Petersen-gráf 3 színnel élszínezhető.[12]

A GP(9,2) azon kevés ismert gráf közé tartozik, melyeknek egyetlen 3-élszínezése létezik.[13]

I-gráfokSzerkesztés

Az általánosított Petersen-gráfok további általánosításának tekinthetők az 1988-as Foster-cenzusban[14] bevezetett I(n, j, k) I-gráfok,[15] ahol a külső sokszög is lehet csillagsokszög. Nevüket arról kapták, hogy az „I” alakot formáló 2 hosszúságú útgráfból állíthatók elő gráfexpanzió segítségével.

Az I(n,j, k) egy olyan gráf, melynek csúcshalmaza

V(I(n,j,k)): {u0, u1, ..., un−1, v0, v1, ..., vn−1},

élhalmaza pedig

E(I(n,j,k)): {ui ui+j, ui vi, vi vi+k: i = 0,...,n − 1},

ahol az általánosság elvesztése nélkül feltehetjük, hogy jk.

Az I(n,1, k) I-gráf megegyezik a GP(n,k) általánosított Petersen-gráffal.

Az I-gráfok tulajdonságaiSzerkesztés

Az I(n, j, k) pontosan akkor összefüggő, ha lnko(n, j, k)=1. Ha lnko(n, j, k) = d > 1, akkor az I(n, j, k) az I(n/d, j/d, k/d) d db kópiájából áll.

Egy összefüggő I(n, j, k) I-gráf pontosan akkor páros, ha n páros, j és k pedig páratlan.

Az I(rn, rj, rk) az I(n,j,k) r kópiájával egyezik meg.

FordításSzerkesztés

  • Ez a szócikk részben vagy egészben a Generalized Petersen graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
  • Ez a szócikk részben vagy egészben a 일반화_페테르센_그래프 című koreai Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

JegyzetekSzerkesztés

  1. Coxeter, H. S. M. (1950), "Self-dual configurations and regular graphs", Bulletin of the American Mathematical Society 56: 413–455, DOI 10.1090/S0002-9904-1950-09407-5.
  2. Watkins, Mark E. (1969), "A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs", Journal of Combinatorial Theory 6: 152–164, DOI 10.1016/S0021-9800(69)80116-X.
  3. Gross, Jonathan L. & Tucker, Thomas W. (1987), Topological Graph Theory, New York: Wiley. Example 2.1.2, p.58.
  4. Campbell, S. R.; Ellingham, M. N. & Royle, Gordon F. (1993), "A characterisation of well-covered cubic graphs", Journal of Combinatorial Mathematics and Combinatorial Computing 13: 193–212.
  5. Frucht, R.; Graver, J. E. & Watkins, M. E. (1971), "The groups of the generalized Petersen graphs", Proceedings of the Cambridge Philosophical Society 70: 211–218, DOI 10.1017/S0305004100049811.
  6. Alspach, B. R. (1983), "The classification of Hamiltonian generalized Petersen graphs", Journal of Combinatorial Theory, Series B 34: 293–312, DOI 10.1016/0095-8956(83)90042-4.
  7. Thomason, Andrew (1982), "Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable", Journal of Graph Theory 6 (2): 219–221, DOI 10.1002/jgt.3190060218.
  8. Schwenk, Allen J. (1989), "Enumeration of Hamiltonian cycles in certain generalized Petersen graphs", Journal of Combinatorial Theory, Series B 47 (1): 53–59, DOI 10.1016/0095-8956(89)90064-6.
  9. Žitnik, Arjana; Horvat, Boris & Pisanski, Tomaž (2010), All generalized Petersen graphs are unit-distance graphs, vol. 1109, IMFM preprints, <http://preprinti.imfm.si/PDF/01109.pdf>.
  10. Steimle, Alice & Staton, William (2009), "The isomorphism classes of the generalized Petersen graphs", Discrete Mathematics 309 (1): 231–237
  11. Ferrero, Daniela & Hanusch, Sarah (2014), "Component connectivity of generalized Petersen graphs", International Journal of Computer Mathematics 91 (9): 1940–1963, ISSN 0020-7160, doi:10.1080/00207160.2013.878023, <http://danielaferrero.wp.txstate.edu/files/2015/03/Component-connectivity-generalized-Petersen-graphs.pdf>. Hozzáférés ideje: 2018-10-20
  12. Castagna, Frank & Prins, Geert Caleb Ernst (1972), "Every generalized Petersen graph has a Tait coloring", Pacific Journal of Mathematics 40, ISSN 0030-8730, DOI 10.2140/pjm.1972.40.53
  13. Bollobás, Béla (2004), Extremal Graph Theory, Dover, p. 233. Reprint of 1978 Academic Press edition.
  14. "The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs", by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) ISBN 0-919611-19-2.
  15. Boben, Marko; Pisanski, Tomaž & Žitnik, Arjana (2005), "I-graphs and the corresponding configurations", Journal of Combinatorial Designs 13 (6): 406–424, DOI 10.1002/jcd.20054.