A Petersen-gráf egy nevezetes speciális gráf. Nagyon gyakran bukkan fel a gráfelméletben különféle állítások ellenpéldájaként. 10 csúcsa és 15 éle van. Bár a névadó Julius Petersen, aki 1898-ban konstruálta meg, ezt a gráfot már 12 évvel Petersen munkája előtt 1886-ban felfedezték.
A gráf konstrukciója Legyen P egy öt elemű halmaz. Ennek a P halmaznak a kételemű részhalmazait feleltetjük meg a gráf csúcsainak. Él akkor van két csúcs között, ha a csúcsoknak megfelelő halmazok diszjunktak. Formálisan:
Az n elemű alaphalmazon hasonlóan konstruált gráfokat Kneser-gráfoknak nevezzük. bélyegkép|jobbra|Ez a gráf is izomorf a Petersen-gráffal. 400px|balra|Petersen-gráf konstrukciója
Petersen motivációja A négyszín-tétel egy ekvivalens alakja, hogy tetszőleges kétszeresen élösszefüggő, 3-reguláris síkgráf élhalmaza három teljes párosításra bontható. Petersen a fenti példával megmutatta, hogy a síkbarajzolhatóság feltétele nem hagyható el. Bebizonyította viszont azt a gyengébb állítást, hogy minden kétszeresen élösszefüggő, 3-reguláris síkgráfban van teljes párosítás.
Hamilton-út és Hamilton-kör A Petersen-gráf csúcstranzitív, van benne Hamilton-út, de nincs Hamilton-kör.
Színezhetőség bélyegkép|jobbra|A Petersen-gráf kromatikus száma 3 A Petersen-gráf 3 színnel színezhető, de kettővel nem (mivel van benne páratlan kör), tehát kromatikus száma 3.
Tulajdonságai A Petersen-gráf: 3-szorosan összefüggő, így 3-szorosan élösszefüggő és hídmentes is. függetlenségi száma 4 és 3 részes (lásd gráfelméleti fogalomtár) 3-reguláris gráf, dominálási száma 3, van teljes párosítása és 2-faktor. 6 különböző teljes teljes párosítása van. a legkisebb olyan 3-reguláris gráf, aminek derékbősége 5. (Az egyedi -cage. Sőt, mivel mindössze 10 csúcsa van, az egyedi -Moore-gráf.). Sugara 2, átmérője 2. A legnagyobb 2 átmérőjű 3-reguláris gráf.Ez következik abból a tényből, hogy Moore-gráf, mivel bármely Moore-gráf a legnagyobb lehetséges reguláris gráf adott fokszámmal és átmérővel. gráfspektruma −2, −2, −2, −2, 1, 1, 1, 1, 1, 3. 2000 feszítőfája van, a legtöbb a 10-csúcsú 3-reguláris gráfok között.; . The cubic graphs with 6 and 8 vertices maximizing the number of spanning trees are Möbius ladders. Kromatikus polinomja Karakterisztikus polinomja , ezért egész spektrumú gráf – olyan gráf, melynek spektruma csak egész számokból áll.
Hivatkozások
Kategória:Gráfelmélet Kategória:Gráfok önálló szócikkel Kategória:Erősen reguláris gráfok