Earl of Holt

Earl of Holt

I en Holt-graf är alla hörn ekvivalenta och alla kanter är likvärdiga, men det finns ingen automorfism som mappar en kant till sig själv med permutation av hörn
Döpt efter Derek F. Holt
Toppar 27
revben 54
Radie 3
Diameter 3
Omkrets 5
Automorfismer 54
Kromatiskt nummer 3
Kromatiskt index 5
Egenskaper vertex-transitiv
kant-transitiv
semi -transitiv
Hamiltonian
Euler
Cayley-graf
 Mediafiler på Wikimedia Commons

Holt -grafen eller Doyle-grafen är den minsta semi-transitiva grafen , det vill säga det minsta exemplet på en vertextransitiv och kanttransitiv graf som inte är symmetrisk [1] [2] . Sådana grafer finns inte ofta [3] . Grafen är uppkallad efter Peter J. Doyle och Derek F. Holt, som självständigt upptäckte grafen 1976 [4] respektive 1981 [5] .

Holt-grafen har diameter 3, radie 3 och omkrets 5, kromatiskt nummer 3, kromatiskt index 5. Grafen är Hamiltonsk med 98 472 olika Hamiltonska cykler [6] . Grafen är 4-vertex-ansluten och 4-kant-ansluten . Den har en bokinbäddning på 3 och ett köantal på 3. [7]

Grafen har en automorfismgrupp av ordningen 54 [6] . Detta är den minsta gruppen för symmetriska grafer med samma antal hörn och kanter. Ritningen av grafen till höger understryker grafens brist på spegelsymmetri.

Det karakteristiska polynomet i grafen är

Galleri

Anteckningar

  1. ↑ Doyle, 1985 .
  2. ↑ Alspach, Marušič, Nowitz, 1994 , sid. 391–402.
  3. ↑ Gross, Yellen, 2004 , sid. 491.
  4. ↑ Doyle, 1976 .
  5. ↑ Holt, 1981 , sid. 201–204.
  6. ↑ 1 2 Weisstein, Eric W. Doyle Graph  (engelska) på Wolfram MathWorld- webbplatsen .
  7. ↑ Jessica Wolz, Engineering Linear Layouts with SAT . Masteruppsats, universitetet i Tübingen, 2018

Litteratur