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
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 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čilnostiUredi

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:

 

UpodobitveUredi

SkliciUredi

ViriUredi

  • Folkman, Jon (1967), "Regular line-symmetric graphs", J. Combin. Th., 3: 215–232, doi:10.1016/S0021-9800(67)80069-3
  • Skiena, S. (1990), Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Reading, MA: Addison-Wesley

Zunanje povezaveUredi