Petersenov graf

Petersenov graf.

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

Slika:Petersen graph, three crossings.png

Petersenov graf s tremi križajočimi povezavami.

Petersenov graf z enako dolgimi povezavami.

Petersenov graf je v teoriji grafov pomemben graf na desetih vozliščih (točkah) z mnogimi zanimivimi lastnostmi. Imenuje se po danskem matematiku Juliusu Petersenu, ki ga vpeljal leta 1892 in objavil leta 1898.

Lastnosti

Osnovne lastnosti

Petersenov graf

• je 3-povezan (stopnja vsakega vozlišča je enaka 3),
• je kubičen, močno regularen,
• ima kromatično število 3 in kromatični indeks 4 in je zato snark.

Druge lastnosti

Petersenov graf

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

Največji in najmanjši

Petersenov graf

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