Holt-gráf
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]
| Holt-gráf v. Doyle-gráf | |
 | |
| A Holt-gráfban a csúcsok ekvivalensek, az élek ekvivalensek, de az élek nem feltétlenül ekvivalensek az inverzeikkel | |
| Névadó | Peter G. Doyle és Derek F. Holt |
| Csúcsok száma | 27 |
| Élek száma | 54 |
| Sugár | 3 |
| Átmérő | 3 |
| Derékbőség | 5 |
| Kromatikus szám | 3 |
| Élkromatikus szám | 5 |
| Automorfizmusok | 54 |
| Egyéb | Csúcstranzitív Éltranzitív Féltranzitív Hamiltoni Euler- Cayley-gráf |
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 98 742 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
szerkesztés-
A Holt-gráf kromatikus száma 3. -
A Holt-gráf élkromatikus száma 5. -
A Holt-gráf Hamilton-gráf.
Jegyzetek
szerkesztés- ↑ Doyle, P. "A 27-Vertex Graph That Is Vertex-Transitive and Edge-Transitive But Not L-Transitive." October 1998. [1]
- ↑ Alspach, Brian; Marušič, Dragan & Nowitz, Lewis (1994), "Constructing Graphs which are ½-Transitive", Journal of the Australian Mathematical Society (Series A) 56 (3): 391–402, doi:10.1017/S1446788700035564, <http://anziamj.austms.org.au/JAMSA/V56/Part3/Alspach.html>. Hozzáférés ideje: 2009-09-06 Archiválva 2003. november 27-i dátummal a Wayback Machine-ben Archivált másolat. [2003. november 27-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. május 16.).
- ↑ Jonathan L. Gross, Jay Yellen, Handbook of Graph Theory, CRC Press, 2004, ISBN 1-58488-090-2, p. 491.
- ↑ Doyle, P. G. (1976), On Transitive Graphs, Senior Thesis, Harvard College. As cited by MathWorld.
- ↑ Holt, Derek F. (1981), "A graph which is edge transitive but not arc transitive", Journal of Graph Theory 5 (2): 201–204, DOI 10.1002/jgt.3190050210.
- ↑ a b Weisstein, Eric W.: Doyle Graph (angol nyelven). Wolfram MathWorld