Petersenov graf

Petersenov graf
Najbolj znana predstavitev Petersenovega grafa s petkotnikom in petimi prečkami.
Ime	Julius Petersen
Točke	10
Povezave	15
Polmer	2
Premer	2
Notranji obseg	5
Avtomorfizem	120 (S5)
Kromatično število	3
Kromatični indeks	4
Ulomljeni kromatični indeks	3
Značilnosti	kubičen krepko-regularen razdaljno-prehoden snark

Petersenov graf. Najbolj znana predstavitev s petimi križajočimi povezavami. Predstavitev Petersenovega grafa je neskončno mnogo.

Petersenov graf z le dvema križajočima povezavama.

Petersenov graf s tremi križajočimi povezavami. Primer lepo kaže kako je ta Petersenov graf izomorfen prvemu in vsem ostalim. Izgleda precej drugače, vendar je z očmi teorije grafov enak drugim.

Petersenov graf s povezavami dolžine 1.

Petersenov graf, ki kaže, da je graf hipohamiltonski. To je posledica dejstva, da je Petersenov graf prehoden po točkah.

Petersenov graf je v teoriji grafov pomemben graf z 10 točkami (vozlišči) in 15 povezavami. Ima mnogo zanimivih značilnosti. Imenuje se po danskem matematiku Juliusu Petersenu, ki ga je vpeljal leta 1892 in objavil leta 1898.

Značilnosti

Osnovne značilnosti

Petersenov graf

• je 3-povezan (stopnja vsake točke je enaka 3),
• je kubičen, krepko-regularen,
• ima kromatično število 3 in kromatični indeks 4 in je zato snark.

Druge značilnosti

Petersenov graf

• je neravninski graf,
• ima najmanjše možno število križajočih povezav 2,
• ima Hamiltonovo pot (Hamiltonov sprehod), ne pa tudi Hamiltonovega cikla,
• je simetričen,
• je Kneserjev graf $K_{5,2}$,
• ima spekter −2, −2, −2, −2, 1, 1, 1, 1, 1, 3 (-2⁴, 1⁵, 3¹),
• ...

Največji in najmanjši

Petersenov graf

• je najmanjši snark,
• je najmanjši kubični graf brez mostov in brez Hamiltonovega cikla,
• je največji kubični graf s premerom 2,
• je najmanjši hipohamiltonski graf.