Holt-gráf
Sablon:Gráf infobox A matematika, közelebbről a gráfelmélet területén a Holt-gráf vagy Doyle-gráf a legkisebb féltranzitív gráf, tehát a legkisebb példa olyan csúcstranzitív és éltranzitív gráfra, ami nem egyben szimmetrikus is.[1][2] Az ilyen gráfok nem túl gyakoriak.[3] Nevét Peter G. Doyle-ról, illetve Derek F. Holtról kapta, akik egymástól függetlenül felfedezték 1976-ban,[4] illetve 1981-ben[5]
A Holt-gráf átmérője 3, sugara 3 és girthparamétere 5, kromatikus száma 3, élkromatikus száma 5 és Hamilton-gráf Sablon:Szám különböző Hamilton-körrel.[6] Továbbá egy 4-szeresen összefüggő és 4-szeresen élösszefüggő gráf
54 automorfizmusból álló automorfizmuscsoportja van.[6] Ez kisebb csoport, mint amennyi egy ugyanennyi csúccsal és éllel rendelkező, de szimmetrikus gráfnak lenne. A jobb oldali ábrán látható is, hogy hiányzik a tükrözési szimmetria.
A Holt-gráf karakterisztikus polinomja:
Galéria
-
A Holt-gráf kromatikus száma 3. -
A Holt-gráf élkromatikus száma 5. -
A Holt-gráf Hamilton-gráf.
Jegyzetek
- ↑ Doyle, P. "A 27-Vertex Graph That Is Vertex-Transitive and Edge-Transitive But Not L-Transitive." October 1998. [1]
- ↑ Sablon:Citation Sablon:Wayback Sablon:Cite web.
- ↑ Jonathan L. Gross, Jay Yellen, Handbook of Graph Theory, CRC Press, 2004, Sablon:ISBN, p. 491.
- ↑ Sablon:Citation. As cited by MathWorld.
- ↑ Sablon:Citation.
- ↑ 6,0 6,1 Sablon:MathWorld