Folkmani graaf

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 .

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 $(x-4)x^{10}(x+4)(x^{2}-6)^{4}$.

Näiteid

• 
  Folkmani graafi kromaatiline klass on 4
• 
  Folkmani graafi kromaatiline number on  2
• 
  Folkmani graaf on Hamiltoni graaf

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 .

Välislingid

• John-Tagore Tevet: Graafide semiootiline modelleerimine