Contele Folkman

Contele Folkman

Contele Folkman
Numit după J. Folkman
Vârfurile douăzeci
coaste 40
Rază 3
Diametru patru
Circumferinţă patru
Automorfisme 3840
Număr cromatic 2
Indicele cromatic patru
Proprietăți Bipartit
Hamiltonian
Semisimetric
Regular
Euler
Perfect
 Fișiere media la Wikimedia Commons

Graficul Folkman (numit după John Folkman) este un graf bipartit 4 - obișnuit cu 20 de vârfuri și 40 de muchii [1] .

Graficul Folkman este hamiltonian și are numărul cromatic 2, indicele cromatic 4, raza 3, diametrul 4 și circumferința 4. Este, de asemenea , conectat la vârf 4 , conectat la muchie 4 și perfect . Graficul are încorporarea cărții 3 și numărul de cozi 2 [2] .

Proprietăți algebrice

Grupul de automorfism al unui graf Folkman acționează tranzitiv asupra muchiilor sale, dar nu asupra vârfurilor sale. Este cel mai mic graf nedirecționat care este tranzitiv la margine și regulat, dar nu tranzitiv la vârf [3] . Astfel de grafuri se numesc semisimetrice , au fost studiate pentru prima dată de Folkman în 1967 și au descoperit un graf cu 20 de vârfuri, care ulterior a fost numit după el [4] .

Ca graf semisimetric, graful Folkman este bipartit și grupul său de automorfism acționează tranzitiv pe fiecare fracțiune de vârfuri din graful bipartit. În diagrama de mai jos, care arată numărul cromatic al unui grafic, vârfurile verzi nu pot fi mapate la roșu prin niciun automorfism, dar orice vârf roșu poate fi mapat la orice alt vârf roșu și orice verde la orice alt vârf verde.

Polinomul caracteristic al graficului Folkman este .

Galerie

Note

  1. ↑ Weisstein, Eric W. Folkman graph  pe site- ul Wolfram MathWorld .
  2. ↑ Volz, 2018 .
  3. ↑ Skiena, 1990 , p. 186-187.
  4. ↑ Folkman, 1967 , p. 215–232.

Literatură