Holt-gráf

a legkisebb féltranzitív 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
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ériaSzerkesztés

JegyzetekSzerkesztés

  1. Doyle, P. "A 27-Vertex Graph That Is Vertex-Transitive and Edge-Transitive But Not L-Transitive." October 1998. [1]
  2. 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.
  3. Jonathan L. Gross, Jay Yellen, Handbook of Graph Theory, CRC Press, 2004, ISBN 1-58488-090-2, p. 491.
  4. Doyle, P. G. (1976), On Transitive Graphs, Senior Thesis, Harvard College. As cited by MathWorld.
  5. 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.
  6. a b Weisstein, Eric W.: Doyle Graph (angol nyelven). Wolfram MathWorld