Folkmanov graf

Iz Wikipedije, proste enciklopedije
Jump to navigation Jump to search
Folkmanov graf
Folkman graph alt.svg
Folkmanov graf
ImeJon Folkman
Točke20
Povezave40
Polmer3
Premer4
Notranji obseg4
Kromatično število2
Kromatični indeks4
Značilnosti4-regularen
(kvartičen)
dvodelen
polsimetričen
Eulerjev
Hamiltonov
popoln

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[uredi | uredi kodo]

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

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[uredi | uredi kodo]

Sklici[uredi | uredi kodo]

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]