Doyle grafikonja | |
A Doyle-gráf ábrázolása | |
Csúcsok száma | 27. |
---|---|
Élek száma | 54. |
Fokozat eloszlás | 4- rendszeres |
Sugár | 3 |
Átmérő | 3 |
Háló | 5. |
Automorfizmusok | 54. |
Kromatikus szám | 3 |
Kromatikus index | 5. |
Tulajdonságok |
Rendszeres Eulerian Hamilton-féle Cayley- csúcs-transzitív Ridge-transzitív |
A Doyle-gráf (vagy Holt-gráf ) a gráfelméletben egy 4-szabályos gráf , 27 csúccsal és 54 éllel. Ez a legkisebb gráfpélda arra, hogy egy gráf csúcstranszitív és éltranszitív, de nem szimmetrikus . Ilyen grafikonok ritkák. Nevét Peter G. Doyle-nak és Derek F. Holtnak köszönheti, akik mindketten függetlenül fedezték fel 1976-ban és 1981-ben.
A Doyle gráf átmérője , csúcsainak maximális excentricitása 3, sugara , csúcsainak minimális excentricitása 3, hálója pedig a legrövidebb ciklus hossza 5. Ez egy 4- csúcsú -összekapcsolt gráfból és egy 4 - szel összekapcsolt gráfból , azaz összekapcsolt állapotban van, és hogy a szétkapcsolódáshoz legalább 4 csúcsot vagy 4 élt el kell vonni.
Ez egy hamiltoni gráf is , 98 472 különálló hamiltoni ciklus.
A Doyle-gráf kromatikus száma 3, vagyis 3 színnel színezhető úgy, hogy egy él által összekötött két csúcs mindig különböző színű legyen, de ez a szám minimális. Nincs érvényes 2 színű grafikon.
A Doyle-gráf kromatikus indexe 5. Ezért a grafikon szélei 5-színűek, így az ugyanazon csúcsra eső két él mindig különböző színű. Ez a szám minimális.
A Doyle gráf automorfizmusainak csoportja az 54. sorrendű csoport.
A karakterisztikus polinomja a szomszédsági mátrix A grafikon Doyle: .