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,^[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.

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.^[3]

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

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]

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).^[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.^[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]

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

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

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

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

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:

${\displaystyle \chi (\operatorname {Gp} (n,k))={\begin{cases}2&2\mid n\land 2\nmid k\\3&2\nmid n\lor 2\mid k\end{cases}}}$

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

• 
  A Petersen-gráf, azaz ${\displaystyle \operatorname {GP} (5,2)}$ 3-színezése
• 
  A Desargues-gráf, azaz ${\displaystyle \operatorname {GP} (10,3)}$ 2-színezése
• 
  A Dürer-gráf, azaz ${\displaystyle \operatorname {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ő.^[12]

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

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

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)): {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(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.

• 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 és a szerzői jogokat 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 és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.