Folkmanov graf
Folkmanov graf je v teoriji grafov neusmerjeni dvodelni regularni graf stopnje 4 z 20-imi točkami in 40-imi povezavami. Imenuje se po Jonu Folkmanu.

Folkmanov graf je Hamiltonov graf in ima kromatično število 2, kromatični indeks 4, premer 4, polmer 3 in notranji obseg 4. Je tudi 4-točkovno-povezan in 4-povezavno-povezan popolni graf.

Algebrske značilnosti 

Folkmanov graf je točkovno-prehoden, ne pa tudi povezavno. Je najmanjši neusmerjeni graf, ki je točkovno-prehoden in regularen, ne pa tudi povezavno-prehoden. Takšni grafi se imenujejo polsimetrični grafi. Prvi jih je raziskoval Folkman leta 1967 in odkril graf z 20-imi točkami, sedaj imenovan po njem.

Kot polsimetrični graf je Folkamnov graf dvodelni graf in ima avtomorfizme za vsak par točk, ne pa za povezave. V spodnji upodobitvi grafa, ki kaže njegovo kromatično število, se zelene točke ne da preslikati v rdeče z nobenim avtomorfizmom. Lahko pa se preslika katerokoli rdečo točko v drugo rdečo točko, ter enako tudi zelene točke.

Folkmanov graf ima 8 različnih posplošenih zapisov LCF, tri z eksponentom 5 in pet z eksponentom 1.

Karakteristični polinom Folkmanovega grafa je:

Upodobitve

Sklici

Viri

Zunanje povezave 

 

Posamezni grafi
Regularni grafi
1967 v znanosti
Folkmanov graf je v teoriji grafov neusmerjeni dvodelni regularni graf stopnjezimi točkami inimi povezavami . Imenuje se po Jonu Folkmanu . Folkmanov graf je Hamiltonov graf in ima kromatično število kromatični indeks premer polmerin notranji obseg Je tuditočkovno - povezan inpovezavno - povezan popolni graf. Algebrske značilnosti Folkmanov graf je točkovno - prehoden , ne pa tudi povezavno . Je najmanjši neusmerjeni graf , ki je točkovno - prehoden in regularen , ne pa tudi povezavno - prehoden . Takšni grafi se imenujejo polsimetrični grafi . Prvi jih je raziskoval Folkman letain odkril graf zimi točkami , sedaj imenovan po njem . Kot polsimetrični graf je Folkamnov graf dvodelni graf in ima avtomorfizme za vsak par točk , ne pa za povezave . V spodnji upodobitvi grafa , ki kaže njegovo kromatično število , se zelene točke ne da preslikati v rdeče z nobenim avtomorfizmom . Lahko pa se preslika katerokoli rdečo točko v drugo rdečo točko , ter enako tudi zelene točke . Folkmanov graf imarazličnih posplošenih zapisov LCF , tri z eksponentomin pet z eksponentom Karakteristični polinom Folkmanovega grafa je : Upodobitve Sklici Viri Zunanje povezave Posamezni grafi Regularni grafi 1967 v znanosti