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 – 

 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 PGL2(7).

 Muid omadusi 

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.

Kategooria:Graafiteooria