Heawoodi graaf

Heawoodi graaf on üks 14 tipu ja 21 servaga lihtgraaf, mis Peterseni graafi kõrval on graafiteoorias teine huvitavate sümmeetriaomadustega tuntud kuupgraaf (st 3-valentsregulaarne). Graaf on nimetatud inglise matemaatiku Percy John Heawoodi järgi.

Üldised parameetrid

Diameeter – 3
Raadius – 3
Automorfismide arv – 336
Kromaatiline number – 2
Kromaatiline indeks – 3
Karakteristlik polünoom – $(x-3)(x+3)(x^{2}-2)^{6}$

Regulaarsused ja sümmeetria

Heawoodi graaf on 3-valentsregulaarne, 3-distantsregulaarne ja 6-vööregulaarne. Kolmevalentseid vööregulaarseid graafe nimetatakse kage’ks (inglise: cage). Iga tipp ja iga serv esineb kahes vöös. Heawoodi graafil on üks tipuorbiit ja üks servaorbiit, st see graaf on tippudest ja servadest transitiivne ehk tugevalt sümmeetriline. Heawoodi graafi sümmeetriamõõt ehk korrapära on 0,766.

Graafi automorfismirühm on PGL₂(7).

Muid omadusi

Heawoodi graafi servade 3-värving

Heawoodi graafi kromaatiline number on 2

Paarisarv vööregulaarsusest tuleneb selle graafi kahealuselisus. Vastavad tipuhulgad moodustavad Heawoodi graafi täiendis kaks (omavahel sidusat, kuid mitte lõikuvat) klikki. Seega on selle 14-tipulise graafi täiend 7-klikkregulaarne.

Kirjandust

A. Buldas, P. Laud, J. Villemson. 2003 Graafid. Tartu, ISBN 9789949118182.
J.-T. Tevet. 2010. Graafide varjatud külgi. SERR, ISBN 9789949213108.
A. Dharwadker, B. Pirzada. 2011. Graph Theory. Amazon Books, ISBN 9781466254992.