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 [1].

Folkmani graaf

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

Parameetreid muuda

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 muuda

Struktuurseid omadusi muuda

  • 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 [2].

Viited muuda

  1. Folkman, J. 1967. Regular line-symmetric graphs. – Journal of Combinatorial Theory, pp 215-232
  2. Tevet, J. 2010. Graafide varjatud külgi. SERR, ISBN 9789949213108

Välislingid muuda