Vizualizare sursă pentru „Graful lui Petersen”

{{Infocaseta Graf
 | name = Graful lui Petersen
 | image = Petersen1 tiny.svg
 | image_size = 200px
 | image_caption = Graful lui Petersen este cel mai adesea desenat ca un pentagon cu o pentagramă în interior, cu cince spițe.
 | namesake = [[Julius Petersen]]
 | vertices = 10
 | edges = 15
 | automorphisms = 120 (S<sub>5</sub>)
 | radius = 2
 | diameter = 2
 | girth = 5
 | chromatic_number = 3
 | chromatic_index = 4
 | fractional_chromatic_index = 3
 | genus = 1
 | properties = [[Graf cubic|Cubic]]<br/>[[Graf tare regulat|Tare regulat]]<br/>[[Graf distanță-tranzitiv|Distanță-tranzitiv]]<br/>[[Snark (teoria grafurilor)|Snark]]
}}
În domeniul [[Matematică|matematic]] al [[Teoria grafurilor|teoriei grafurilor]], '''graful lui Petersen''' este un [[Graf|graf neorientat]] cu 10 [[Nod (teoria grafurilor)|noduri]] și 15 [[Glosar de teoria grafurilor|muchii]]. Este un graf mic care servește drept exemplu și [[contraexemplu]] util pentru multe probleme din teoria grafurilor. Graful lui Petersen este numit după [[Julius Petersen]], care în 1898 l-a construit în așa fel încât să fie cel mai mic [[graf cubic]] [[Punte (teoria grafurilor)|fără punți]] care nu are 3-colorări de muchii.<ref>{{Citation|last=Brouwer|first=Andries E.|title=The Petersen graph|url=http://www.win.tue.nl/~aeb/drg/graphs/Petersen.html|author-link=Andries Brouwer}}</ref><ref>{{Citation|last=Petersen|first=Julius|title=Sur le théorème de Tait|url=https://archive.org/details/lintermdiairede03lemogoog/page/n239/mode/1up?view=theater|volume=5|pages=225&ndash;227|year=1898|periodical=[[L'Intermédiaire des Mathématiciens]]|author-link=Julius Petersen}}</ref>

Deși graful este în general creditat lui Petersen, de fapt a apărut pentru prima dată cu 12 ani mai devreme, într-o lucrare a lui {{Harvard citations|first=A. B.| last=Kempe |authorlink=Alfred Kempe|year=1886|txt}}. Kempe a observat că nodurile sale pot reprezenta cele zece linii ale [[Configurație Desargues|configurației lui Desargues]], iar muchiile sale reprezintă perechi de linii care nu se întâlnesc într-unul dintre cele zece puncte ale configurației.<ref>{{Citation|last=Kempe|first=A. B.|title=A memoir on the theory of mathematical form|volume=177|pages=1&ndash;70|year=1886|periodical=Philosophical Transactions of the Royal Society of London|doi=10.1098/rstl.1886.0002}}</ref>

[[Donald E. Knuth|Donald Knuth]] afirmă că graful lui Petersen este „o configurație remarcabilă care servește ca un contraexemplu pentru multe predicții optimiste despre ceea ce ar putea fi adevărat pentru grafuri în general”.<ref>{{Citation|last=Knuth|first=Donald E.|title=The Art of Computer Programming; volume 4, pre-fascicle 0A. A draft of section 7: Introduction to combinatorial searching}}</ref>

Graful lui Petersen apare, de asemenea, în [[Geometrie tropicală|geometria tropicală]]. Conul de deasupra grafului lui Petersen este identificat în mod natural cu spațiul de module al curbelor tropicale raționale 5-punctate.

== Construcții ==
[[Fișier:Kneser_graph_KG(5,2).svg|stanga|miniatura| Graful lui Petersen ca graf Kneser <math>KG_{5,2}</math>]]
Graful lui Petersen este [[graf complementar|complementul]] [[Graf linie|grafului linie]] al lui <math>K_5</math>. Este de asemenea [[Graf Kneser|graful Kneser]] <math>KG_{5,2}</math>; aceasta înseamnă că are un nod pentru fiecare submulțime cu 2 elemente a unei mulțimi cu 5 elemente, iar două noduri sunt conectate printr-o muchie dacă și numai dacă submulțimile corespunzătoare cu 2 elemente sunt disjuncte. Fiind un graf Kneser de forma <math>KG_{2n-1,n-1}</math>, este un exemplu de [[graf impar]].

Din punct de vedere geometric, graful lui Petersen este graful format din nodurile și muchiile [[Hemidodecaedru|semi-dodecaedrului]], adică un [[dodecaedru]] cu punctele, liniile și fețele opuse identificate împreună.

== Scufundări ==
Graful lui Petersen este [[Graf planar|neplanar]]. Orice graf neplanar are ca [[minor de graf|minori]] [[Graf complet|graful complet]] <math>K_5</math> sau [[graf bipartit complet|graful bipartit complet]] <math>K_{3,3}</math>, iar graful lui Petersen le are pe amândouă. Minorul <math>K_5</math> poate fi format prin contractarea muchiilor unui [[cuplaj perfect]], de exemplu cele cinci muchii scurte din prima imagine. Minorul <math>K_{3,3}</math> poate fi format prin ștergerea unui nod (de exemplu nodul central al desenului 3-simetric) și contractarea unei muchii incidente la fiecare vecin al nodului șters.
[[Fișier:Petersen_graph,_two_crossings.svg|dreapta|miniatura| Graful lui Petersen are [[Numărul încrucișat (teoria graficelor)|numărul de încrucișare]] 2 și este [[1-graf planar|1-planar]].]]
Cel mai comun și simetric desen plan al grafului lui Petersen, ca pentagramă într-un pentagon, are cinci încrucișări. Totuși, acesta nu este cel mai bun desen pentru minimizarea încrucișărilor; există alt desen (prezentat în figură) cu doar două încrucișări. Deoarece este neplanar, are cel puțin o încrucișare în orice desen, iar dacă o muchie încrucișată este îndepărtată din orice desen, rămâne neplanar și are o altă încrucișare; prin urmare, numărul său de încrucișare este exact 2. Fiecare muchie din acest desen este încrucișată cel mult o dată, deci graful lui Petersen este [[1-graf planar|1-planar]]. Pe un [[tor]] graful lui Petersen poate fi desenat fără încrucișări de muchii; are prin urmare [[Gen (matematică)|genul orientabil]] 1.
[[Fișier:Petersen_graph,_unit_distance.svg|dreapta|miniatura| Graful lui Petersen este un [[Graficul distanței unității|graf cu distanțe unu]]: poate fi desenat în plan, fiecare muchie având lungimea unu.]]
De asemenea, graful lui Petersen poate fi desenat (cu încrucișări) în plan în așa fel încât toate muchiile să aibă lungime egală. Adică este un [[graf cu distanțe unu]].

Cea mai simplă [[Suprafață (matematică)|suprafață neorientabilă]] în care poate fi scufundat graful lui Petersen fără încrucișări este [[plan proiectiv|planul proiectiv]]. Aceasta este scufundarea dată de construcția [[Hemidodecaedru|semi-dodecaedrului]] grafului lui Petersen (prezentat în figură). Scufundarea în planul proiectiv mai poate fi formată din desenul pentagonal standard al grafului lui Petersen prin plasarea unui [[Banda lui Möbius|capac încrucișat]] în cadrul stelei cu cinci puncte în centrul desenului și direcționarea muchiilor stelei prin acest capac încrucișat; desenul rezultat are șase fețe pentagonale. Această construcție formează o [[aplicație regulată]] și arată că graful lui Petersen are [[Gen (matematică)|genul 1 neorientabil]].
[[Fișier:Petersen-graph.png|miniatura| Graful lui Petersen și aplicația asociată scufundate în [[plan proiectiv|planul proiectiv]]. Punctele opuse de pe cerc sunt identificate, rezultând o suprafață închisă neorientabilă de gen 1.]]

== Simetrii ==
Graful lui Petersen este [[graf tare regulat|tare regulat]] (cu signatura srg(10,3,0,1)). Este de asemenea [[Graf simetric|simetric]], adică este [[graf muchie-tranzitiv|muchie-tranzitiv]] și [[graf nod-tranzitiv|nod-tranzitiv]]. Mai mult, este 3-arc-tranzitiv: orice drum orientat din trei muchii în graful lui Petersen poate fi transformat în orice alt astfel de drum printr-o simetrie a grafului.<ref>{{Citation|last=Babai|first=László|title=Handbook of Combinatorics|url=http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps|volume=I|pages=1447–1540|year=1995|editor-last=Graham|editor-first=Ronald L.|archive-url=https://web.archive.org/web/20100611212234/http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps|chapter=Automorphism groups, isomorphism, reconstruction|publisher=North-Holland|id=Corollary 1.8|archive-date=2010-06-11|author-link=László Babai|editor2-last=Grötschel|editor2-first=Martin|editor3-last=Lovász|editor3-first=László|editor1-link=Ronald Graham|editor2-link=Martin Grötschel|editor3-link=László Lovász}}.</ref> Este unul dintre cele 13 grafuri cubice [[graf distanță-regulat|distanță-regulate]].<ref name="foster">Royle, G. [http://www.cs.uwa.edu.au/~gordon/remote/foster/#census "Cubic Symmetric Graphs (The Foster Census)."] {{Webarchive|url=https://web.archive.org/web/20080720005020/http://www.cs.uwa.edu.au/~gordon/remote/foster/|date=2008-07-20}}</ref>

[[automorfism de graf|Grupul de automorfisme]] al grafului lui Petersen este [[grup simetric|grupul simetric]] <math>S_5</math>; actiunea lui <math>S_5</math> pe graful lui Petersen rezultă din construcția sa ca [[Graf Kneser|graf Kneser]]. Graful lui Petersen este un [[Nucleu (teoria grafurilor)|nucleu]]: orice [[Morfism de grafuri|morfism]] de la grafului lui Petersen la el însuși este un automorfism.<ref>{{Citation|last=Cameron|first=Peter J.|title=Topics in Algebraic Graph Theory|volume=102|pages=135–153|year=2004|editor-last=Beineke|editor-first=Lowell W.|series=Encyclopedia of Mathematics and its Applications|chapter=Automorphisms of graphs|publisher=Cambridge University Press, Cambridge|doi=10.1017/CBO9780511529993|isbn=0-521-80197-4|mr=2125091|editor2-last=Wilson|editor2-first=Robin J.}}; vezi în special [https://books.google.com/books?id=z2K26gZLC1MC&pg=PA153 p. 153]</ref> După cum se vede în figuri, desenele grafului lui Petersen pot prezenta simetrie în cinci sau trei sensuri, dar nu este posibilă desenarea grafului lui Petersen în plan în așa fel încât desenul să prezinte grupul de simetrie complet al grafului.

În ciuda gradului său ridicat de simetrie, graful lui Petersen nu este un [[graf Cayley]]. Este cel mai mic graf nod-tranzitiv care nu este un graf Cayley.{{Efn|Așa cum este formulat, aceasta presupune că grafurile Cayley nu trebuie să fie neapărat conexe. Unele surse impun ca grafurile Cayley să fie conexe, ceea ce face [[graf vid|graful vid]] cu două noduri să fie cel mai mic graf non-Cayley nod-tranzitiv; în raport cu definiția dată de aceste surse, graful lui Petersen este cel mai mic graf nod-tranzitiv conex care nu este Cauchy.}}

== Drumuri și cicluri hamiltoniene ==
[[Fișier:Petersen2_tiny.svg|dreapta|miniatura| Graful lui Petersen este hipo-Hamiltonian: prin ștergerea oricărui nod, cum ar fi nodul central din desen, graful rămas este hamiltonian. Acest desen cu simetrie de ordin 3 este cel dat de Kempe (1886).]]
Graful lui Petersen are un [[drum hamiltonian]], dar nu are [[Drum hamiltonian|cicluri hamiltoniene]]. Este cel mai mic graf cubic fără punți, fără cicluri hamiltoniene. Este [[Graf hipohamiltonian|hipohamiltonian]], ceea ce înseamnă că, deși nu are niciun ciclu hamiltonian, ștergerea oricărui nod îl face hamiltonian și este cel mai mic graf hipohamiltonian.

Fiind un graf nod-tranzitiv conex finit care nu are niciun ciclu hamiltonian, graful lui Petersen este un contraexemplu pentru o variantă a [[Conjectura Lovász|conjecturii lui Lovász]], dar formularea canonică a conjecturii cere un drum hamiltonian și este verificată de graful lui Petersen.

Sunt cunoscute doar cinci grafuri nod-tranzitive conexe fără cicluri hamiltoniene: [[Graf complet|graful complet]] ''K''<sub>2</sub>, graful lui Petersen, [[graful lui Coxeter]] și două grafuri derivate din grafurile lui Petersen și Coxeter prin înlocuirea fiecărui nod cu un triunghi.<ref name="foster">Royle, G. [http://www.cs.uwa.edu.au/~gordon/remote/foster/#census "Cubic Symmetric Graphs (The Foster Census)."] {{Webarchive|url=https://web.archive.org/web/20080720005020/http://www.cs.uwa.edu.au/~gordon/remote/foster/|date=2008-07-20}}</ref> Dacă ''G'' este un graf 2-conex, ''r''-regulat cu cel mult 3''r''&nbsp;+&nbsp;1 noduri, atunci ''G'' este hamiltonian sau este graful lui Petersen.<ref>{{Citation|last=Holton|first=D. A.|title=The Petersen Graph|page=32|year=1993|publisher=[[Cambridge University Press]]|isbn=0-521-43594-3|last2=Sheehan|first2=J.}}</ref>

Pentru a vedea că graful lui Petersen nu are niciun ciclu hamiltonian, se consideră muchiile din tăietura care deconectează 5-ciclul interior de cel exterior. Dacă există un ciclu hamiltonian ''C'', acesta trebuie să conțină un număr par din aceste muchii. Dacă conține doar două dintre ele, nodurile lor trebuie să fie adiacente în cele două 5-cicluri, ceea ce nu este posibil. Prin urmare, conține exact patru dintre ele. Să presupunem că muchia superioară a tăieturii nu este conținută în ''C'' (toate celelalte cazuri sunt identice prin simetrie). Dintre cele cinci muchii din ciclul exterior, cele două muchii superioare trebuie să fie în ''C'', cele două muchii laterale trebuie să nu fie în ''C'', prin urmare, muchia inferioară trebuie să fie în ''C''. Cele două muchii de sus din ciclul interior trebuie să fie în ''C'', dar acest lucru completează un ciclu care nu este de acoperire, care nu poate face parte dintr-un ciclu hamiltonian. Alternativ, putem de asemenea descrie [[Graf regulat|grafurile 3-regulate]] cu 10 noduri care au un ciclu hamiltonian și să arătăm că niciunul dintre ele nu este graful lui Petersen, găsind în fiecare dintre ele un ciclu mai scurt decât orice ciclu din graful lui Petersen. Orice graf 3-regulat hamiltonian cu 10 noduri constă dintr-un ciclu ''C'' cu 10 noduri plus 5 coarde. Dacă orice coardă unește două noduri la distanța 2 sau 3 de-a lungul lui ''C'', graful are un ciclu de 3 sau 4 cicluri și, prin urmare, nu poate fi graful lui Petersen. Dacă două coarde unesc noduri opuse ale lui ''C'' de noduri la distanța 4 de-a lungul lui ''C'', există din nou un 4-ciclu. Singurul caz rămas este o [[scară Möbius]] formată prin unirea fiecărei perechi de noduri opuse printr-o coardă, care are din nou un 4-ciclu. Deoarece graful lui Petersen are grosimea 5, nu poate fi format în acest fel și nu are ciclu hamiltonian.

== Colorare ==
[[Fișier:PetersenBarveniHran.svg|stanga|miniatura| O 4-colorare a muchiilor grafului lui Petersen]]
[[Fișier:Petersen_graph_3-coloring.svg|dreapta|miniatura| O 3-colorare a nodurilor grafului lui Petersen]]
Graful lui Petersen are [[Colorarea grafurilor|numărul cromatic]] 3, ceea ce înseamnă că nodurile sale pot fi [[Colorarea grafurilor|colorate]] cu trei culori – dar nu cu două – astfel încât nicio muchie să nu unească noduri de aceeași culoare. Are o [[colorare de listă]] cu 3 culori, conform teoremei lui Brooks pentru colorări de liste.

Graful lui Petersen are [[indice cromatic|indicele cromatic]] 4; colorarea marginilor necesită patru culori. Fiind un graf cubic fără punți și conex cu indice cromatic 4, graful lui Petersen este un [[Snark (teoria grafurilor)|snark]]. Este cel mai mic snark posibil și a fost singurul snark cunoscut din 1898 până în 1946. [[Snark (teoria grafurilor)|Teorema snarkurilor]], un rezultat conjecturat de [[William Tutte|W. T. Tutte]] și anunțat în 2001 de Robertson, Sanders, Seymour și Thomas,<ref>{{Citation|last=Pegg|first=Ed Jr.|title=Book Review: The Colossal Book of Mathematics|url=https://www.ams.org/notices/200209/rev-pegg.pdf|volume=49|issue=9|pages=1084–1086|year=2002|periodical=Notices of the American Mathematical Society|bibcode=2002ITED...49.1084A|doi=10.1109/TED.2002.1003756|author-link=Ed Pegg, Jr.}}</ref> afirmă că fiecare snark are graful lui Petersen ca [[minor de graf|minor]].

În plus, graful are [[Indice cromatic fracționar|indicele cromatic fracționar]] 3, demonstrând că diferența dintre indicele cromatic și indicele cromatic fracționar poate fi 1. [[Conjectura Goldberg-Seymour]] afirmă că acesta este cea mai mare diferență posibilă.

[[Număr Thue|Numărul Thue]] (o variantă a indexului cromatic) al grafului lui Petersen este 5.

Graful lui Petersen necesită cel puțin trei culori în orice colorare (posibil improprie) care rupe toate simetriile sale; adică [[Număr distinctiv|numărul său distinctiv]] este trei. Cu excepția grafurilor complete, este singurul graf Kneser al cărui număr distinctiv nu este 2.<ref>{{Citation|last=Albertson|first=Michael O.|title=Using determining sets to distinguish Kneser graphs|volume=14|issue=1|page=R20|year=2007|periodical=Electronic Journal of Combinatorics|doi=10.37236/938|mr=2285824|last2=Boutin|first2=Debra L.|author-link2=Debra Boutin|doi-access=free}}.</ref>

== Alte proprietăți ==
Graful lui Petersen:

* este 3-conex și, prin urmare, 3-muchie-conex și fără punți. A se vedea [[Glosar de teoria grafurilor|glosarul]].
* are numărul de independență 4 și este tripartit. A se vedea [[Glosar de teoria grafurilor|glosarul]].
* este [[Graf cubic|cubic]], are [[număr de dominație|numărul de dominație]] 3 și are un [[cuplaj perfect]] și un [[Factor (teoria grafurilor)|2-factor]].
* are 6 cuplaje perfecte distincte.
* este cel mai mic graf cubic de [[Grosime (teoria grafurilor)|grosime]] 5. (Este unica <math>(3,5)</math>-[[Cușcă (teoria graficelor)|cușcă]]. De fapt, din moment ce are doar 10 noduri, este unicul graf <math>(3,5)</math>-[[Graf Moore|Moore]].)<ref name="hs60">{{Citation|last=Hoffman|first=Alan J.|title=Moore graphs with diameter 2 and 3|url=http://www.research.ibm.com/journal/rd/045/ibmrd0405H.pdf|volume=5|issue=4|pages=497–504|year=1960|periodical=IBM Journal of Research and Development|doi=10.1147/rd.45.0497|mr=0140437|last2=Singleton|first2=Robert R.|author-link=Alan Hoffman (mathematician)}}.</ref>
* orice graf cubic fără punți și fără minori Petersen are o acoperire dublă cu cicluri.<ref>{{Citation|last=Alspach|first=Brian|title=Cycle covers of cubic multigraphs|volume=111|pages=11–17|year=1993|periodical=Discrete Math.|last2=Zhang|first2=Cun-Quan|author-link=Brian Alspach (mathematician)}}.</ref>
* este cel mai mic graf cubic cu [[invariantul Colin de Verdière]] μ = 5.<ref>{{Citation|last=László Lovász, Alexander Schrijver|title=A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs|url=https://www.ams.org/journals/proc/1998-126-05/S0002-9939-98-04244-0/S0002-9939-98-04244-0.pdf|volume=126|issue=5|pages=1275–1285|year=1998|periodical=[[Proceedings of the American Mathematical Society]]|doi=10.1090/S0002-9939-98-04244-0}}</ref>
* are [[Rază (teoria grafurilor)|raza]] 2 și [[Diametru (teoria grafurilor)|diametrul]] 2. Este cel mai mare graf cubic cu diametrul 2.{{Efn|Aceasta rezultă din faptul că este un graf Moore, întrucât orice graf Moore este cel mai mare graf regulat posibil cu gradul său și diametrul său.<ref name="hs60"/>}}
* are 2000 de [[arbore de acoperire|arbori de acoperire]], cel mai mult din orice graf cubic cu 10 noduri.<ref>{{Citation|last=Jakobson|first=Dmitry|title=On some extremal problems in graph theory|year=1999|arxiv=math.CO/9907050|bibcode=1999math......7050J|last2=Rivin|first2=Igor}}
</ref><ref>{{Citation|last=Valdes|first=L.|title=Extremal properties of spanning trees in cubic graphs|volume=85|pages=143–160|year=1991|periodical=Congressus Numerantium}}.
</ref>{{Efn|Grafurile cubice cu 6 și 8 noduri care maximizează numărul de arbori de acoperire sunt [[scară Möbius|scările Möbius]].}}
* are [[polinom cromatic|polinomul cromatic]] <math>t(t-1)(t-2)\left(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352\right)</math>.<ref name="biggs">{{Citation|last=Biggs, Norman|title=Algebraic Graph Theory|year=1993|edition=2nd|place=Cambridge|publisher=Cambridge University Press|isbn=0-521-45897-8}}</ref>
* are [[polinom caracteristic|polinomul caracteristic]] <math>(t-1)^5(t+2)^4(t-3)</math>, făcându-l un [[graf integral]] — un graf al cărui [[teoria spectrală a grafurilor|spectru]] este format în întregime din numere întregi.

== Conjectura de colorare a lui Petersen ==
Un ''subgraf eulerian'' al unui graf <math>G</math> este un subgraf format dintr-o submulțime de muchii ale lui <math>G</math>, atingând fiecare nod al lui <math>G</math> de un număr par de ori. Aceste subgrafuri sunt elementele [[Spațiu ciclu|spațiului ciclu]] al lui <math>G</math> și sunt numite uneori cicluri. Dacă <math>G</math> și <math>H</math> sunt oricare două grafuri, o funcție de la muchiile lui <math>G</math> la muchiile lui <math>H</math> este definită a fi ''ciclu-continuă'' dacă preimaginea fiecărui ciclu al lui <math>H</math> este un ciclu al lui <math>G</math>. O conjectură a lui Jaeger afirmă că orice graf fără punți are o aplicație ciclu-continuă la graful lui Petersen. Jaeger a arătat că această conjectură implică conjectura de [[Acoperire dublă cu cicluri|acoperire dublă]] cu 5-cicluri și conjectura Berge-Fulkerson.<ref>{{Citation|last=DeVos|first=Matt|title=Graph theory in Paris|pages=109–138|year=2007|series=Trends Math.|chapter=On edge-maps whose inverse preserves flows or tensions|place=Basel|publisher=Birkhäuser|doi=10.1007/978-3-7643-7400-6_10|isbn=978-3-7643-7228-6|mr=2279171|last2=Nešetřil|first2=Jaroslav|last3=Raspaud|first3=André|author-link2=Jaroslav Nešetřil}}.</ref>

== Grafuri înrudite ==
[[Fișier:Petersen_family.svg|miniatura| [[familia Petersen|Familia Petersen]].]]
[[Graf Petersen generalizat|Graful Petersen generalizat]] <math>G(n,k)</math> se formează prin unirea nodurilor unui [[Poligon regulat|''n''-gon regulat]] la nodurile corespunzătoare ale unui [[Poligon stelat|poligon stea]] cu [[Simbol Schläfli|simbolul Schläfli]] {''n''/''k''}.<ref>{{Citation|last=Coxeter|first=H. S. M.|title=Self-dual configurations and regular graphs|volume=56|issue=5|pages=413–455|year=1950|periodical=[[Bulletin of the American Mathematical Society]]|doi=10.1090/S0002-9904-1950-09407-5|author-link=Harold Scott MacDonald Coxeter|doi-access=free}}.
</ref><ref>{{Citation|last=Watkins|first=Mark E.|title=A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs|volume=6|issue=2|pages=152&ndash;164|year=1969|periodical=[[Journal of Combinatorial Theory]]|doi=10.1016/S0021-9800(69)80116-X|doi-access=free}}</ref> De exemplu, în această notație, graful lui Petersen este <math>G(5,2)</math>: poate fi format prin unirea nodurilor corespunzătoare ale unui pentagon și ale unei stele cu cinci puncte, iar muchiile din stea unesc fiecare al doilea nod. Grafurile Petersen generalizate includ, de asemenea, ''n''-prisma <math>G(n,1)</math>, [[graful lui Dürer]] <math>G(6,2)</math>, [[graful Möbius-Kantor]] <math>G(8,3)</math>, [[Dodecaedru|dodecaedrul]] <math>G(10,2)</math>, [[graful lui Desargues]] <math>G(10,3)</math> și [[graful lui Nauru]] <math>G(12,5)</math>.

[[Familie Petersen|Familia Petersen]] este formată din cele șapte grafuri care pot fi formate din graful lui Petersen prin zero sau mai multe aplicări de [[Transformarea Y-Δ|transformări Δ-Y sau Y-Δ]]. [[Graf complet|Graful complet]] ''K''<sub>6</sub> este de asemenea în familia Petersen. Aceste grafuri formează [[Minor interzis|minorii interziși]] pentru [[Scufundare fără legături|grafurile scufundabile fără legături]], grafuri care pot fi scufundate în spațiul tridimensional astfel încât oricare două cicluri să nu fie [[Legătură (teoria nodurilor)|legate]].<ref name="Bailey1997">{{Citation|last=Bailey|first=Rosemary A.|title=Surveys in Combinatorics|page=187|year=1997|publisher=Cambridge University Press|isbn=978-0-521-59840-8}}</ref>

[[Graful lui Clebsch]] conține multe copii ale grafului lui Petersen ca [[Subgraf indus|subgrafuri induse]]: pentru fiecare nod ''v'' al grafului lui Clebsch, cei zece non-vecini ai lui ''v'' induc o copie a grafului lui Petersen.{{Clear}}

== Note explicative ==
{{Notelist}}

== Note ==
<references />

== Lectură suplimentară ==
* {{Citation|last=Exoo|first=Geoffrey|title=The crossing numbers of some generalized Petersen graphs|volume=48|pages=184&ndash;188|year=1981|periodical=Mathematica Scandinavica|doi=10.7146/math.scand.a-11910|last2=Harary|first2=Frank|last3=Kabell|first3=Jerald|author-link2=Frank Harary|doi-access=free}}.
* {{Citation|last=Lovász|first=László|title=Combinatorial Problems and Exercises|year=1993|edition=2nd|publisher=North-Holland|isbn=0-444-81504-X|author-link=László Lovász}}.
* {{Citation|last=Schwenk|first=A. J.|title=Enumeration of Hamiltonian cycles in certain generalized Petersen graphs|volume=47|issue=1|pages=53&ndash;59|year=1989|series=Series B|periodical=[[Journal of Combinatorial Theory]]|doi=10.1016/0095-8956(89)90064-6|doi-access=free}}
*{{citation
 | last = Zhang
 | first = Cun-Quan
 | isbn = 978-0-8247-9790-4
 | publisher = CRC Press
 | title = Integer Flows and Cycle Covers of Graphs
 | year = 1997
 | url-access = registration
 | url = https://archive.org/details/integerflowscycl0000zhan
 }}.
* {{Citation|last=Zhang|first=Cun-Quan|title=Circuit Double Cover of Graphs|year=2012|publisher=Cambridge University Press|isbn=978-0-5212-8235-2}}.

== Legături externe ==
* {{MathWorld|urlname=PetersenGraph|title=Petersen Graph}}
* [http://oeis.org/search?q=Petersen+Graph&sort=&language=english&go=Search Petersen Graph] la [[Enciclopedia electronică a șirurilor de numere întregi]]

{{Control de autoritate}}
[[Categorie:Grafuri individuale]]
[[Categorie:Teoria grafurilor]]