Általánosított Petersen-gráf

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

A GP(12,4).

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ó.

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

Definíció és jelölések

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

V(GP(n,k)): {u₀, u₁, ..., u_n−1, v₀, v₁, ..., v_n−1},

élhalmaza pedig

E(GP(n,k)): {u_i u_i+1, u_i v_i, v_i v_i+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.

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

Példák

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ű).

Tulajdonságok

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 k² ≡ ±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). 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 k² ≡ 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. Ha n ≡ 3 modulo 6 és k értéke 2, GP(n,k)-nak pontosan három Hamilton-köre van. 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.

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

Izomorfizmusok

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

Girthparaméter

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)) ≤ $\min \{8,k+3,n/\gcd \{n,k\}\}$.

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

Feltétel	Girth
$n=3k$	3
$n=4k$	4
$k=1$
$n=5k$	5
$n=5k/2$
$k=2$
$n=6k$	6
$k=3$
$n=2k+2$
$n=7k$	7
$n=7k/2$
$n=7k/3$
$k=4$
$n=2k+3$
$n=3k\pm 2$
Egyéb esetben	8

Kromatikus szám és élkromatikus szám

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:

$\chi (\mathrm{Gp}(n,k))=\{\begin{array}{cc}2& 2\mid n\wedge 2\nmid k\\ 3& 2\nmid n\vee 2\mid k\end{array}$

Ahol $\wedge$ a logikai ÉS, $\vee$ pedig a logikai VAGY jelölése. Például a $\mathrm{GP}(5,2)$ esetén a kromatikus szám 3.

• 
  A Petersen-gráf, azaz $\mathrm{GP}(5,2)$ 3-színezése
• 
  A Desargues-gráf, azaz $\mathrm{GP}(10,3)$ 2-színezése
• 
  A Dürer-gráf, azaz $\mathrm{GP}(6,2)$ 3-színezése

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ő.

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

• 
  A Petersen-gráf, azaz $\mathrm{GP}(5,2)$ 4-élszínezése
• 
  A Dürer-gráf, azaz $\mathrm{GP}(6,2)$ 3-élszínezése
• 
  A dodekaéder, azaz $\mathrm{GP}(10,2)$ 3-élszínezése
• 
  A Desargues-gráf, azaz $\mathrm{GP}(10,3)$ 3-élszínezése
• 
  A Nauru-gráf, azaz $\mathrm{GP}(12,5)$ 3-élszínezése

I-gráfok

Az általánosított Petersen-gráfok további általánosításának tekinthetők az 1988-as Foster-cenzusban bevezetett I(n, j, k) I-gráfok, 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)): {u₀, u₁, ..., u_n−1, v₀, v₁, ..., v_n−1},

élhalmaza pedig

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

ahol az általánosság megszorítása nélkül feltehetjük, hogy j ≤ k.

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

Az I-gráfok tulajdonságai

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ás

• Sablon:Fordítás
• Sablon:Fordítás