Hrabě z Holt

hrabě z Holt

V Holt grafu jsou všechny vrcholy ekvivalentní a všechny hrany ekvivalentní, ale neexistuje žádný automorfismus, který by mapoval hranu na sebe s permutací vrcholů.
Pojmenoval podle Derek F. Holt
Vrcholy 27
žebra 54
Poloměr 3
Průměr 3
obvod 5
Automorfismy 54
Chromatické číslo 3
Chromatický index 5
Vlastnosti vertex-tranzitivní
hraně-tranzitivní
semi -tranzitivní
Hamiltonův
Euler
Cayleyův graf
 Mediální soubory na Wikimedia Commons

Holtův graf nebo Doyleův graf je nejmenší semitranzitivní graf , tedy nejmenší příklad vertexově tranzitivního a hraně tranzitivního grafu, který není symetrický [1] [2] . Takové grafy se často nenacházejí [3] . Graf je pojmenován po Peteru J. Doyleovi a Dereku F. Holtovi, kteří nezávisle na sobě graf objevili v roce 1976 [4] a 1981 [5] .

Holtův graf má průměr 3, poloměr 3 a obvod 5, chromatické číslo 3, chromatický index 5. Graf je hamiltonovský s 98 472 různými hamiltonovskými cykly [6] . Graf je spojen se 4 vrcholy a se 4 okraji . Má vložení knihy 3 a počet ve frontě 3. [7]

Graf má automorfní grupu řádu 54 [6] . Toto je nejmenší skupina pro symetrické grafy se stejným počtem vrcholů a hran. Kresba grafu vpravo zdůrazňuje nedostatek zrcadlové symetrie grafu.

Charakteristickým polynomem grafu je

Galerie

Poznámky

  1. ↑ Doyle, 1985 .
  2. ↑ Alspach, Marušič, Nowitz, 1994 , s. 391–402.
  3. ↑ Gross, Yellen, 2004 , str. 491.
  4. ↑ Doyle, 1976 .
  5. ↑ Holt, 1981 , str. 201–204.
  6. ↑ 1 2 Weisstein, Eric W. Doyle Graph  (anglicky) na webu Wolfram MathWorld .
  7. ↑ Jessica Wolz, Engineering Linear Layouts with SAT . Diplomová práce, Univerzita v Tübingenu, 2018

Literatura