Folkmani graaf

Folkmani graaf on väikseim semi-sümmeetriline graaf. See on saanud nime ameerika matemaatiku Jon Folkmani (1938–1969) järgi, kes selle graafi baasil täpsustas probleemi graafi tipusümmeetria ja servasümmeetria vahekorrast Folkman, J. 1967. Regular line-symmetric graphs. – Journal of Combinatorial Theory, pp 215-232.

Folkmani graaf on kahealuseline, servadest sümmeetriline kuid tippudest mittesümmeetriline graaf, mis tähendabki semi-sümmeetrilisust.

 Parameetreid 
Folkmani graafil on 20 tippu ja 40 serva. See on 4-valentsregulaarne ja 4-vööregulaarne Hamiltoni graaf, selle kromaatiline arv on 2, kromaatiline klass 4 ning diameeter 4.

Folkmani graafi karakteristlik polünoom on .

 Näiteid 

 Struktuurseid omadusi 
 Folkmani graafi kahealuselisusest johtub, et selle täiend on 10-klikkregulaarne koosnedes kahest omavahel sidusast 10-klikist.
 Folkmani graafil on kuus binaarorbiiti, sh üks serva- ja viis "mitteserva" orbiiti. Selle ühele "mitteserva" orbiidile (st täiendi ühele binaarorbiidile) vastav orbiitgraaf osutub Peterseni graafiks, teisele orbiidile vastav aga selle täiendiks Tevet, J. 2010. Graafide varjatud külgi. SERR, ISBN 9789949213108.

 Viited 

 Välislingid 
 John-Tagore Tevet: Graafide semiootiline modelleerimine

Kategooria:Graafiteooria