Ugrás a tartalomhoz

Holt-gráf

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából
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áma27
Élek száma54
Sugár3
Átmérő3
Derékbőség5
Kromatikus szám3
Élkromatikus szám5
Automorfizmusok54
EgyébCsúcstranzitív
Éltranzitív
Féltranzitív
Hamiltoni
Euler-
Cayley-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]

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]

Jegyzetek

[szerkeszté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 Archivált másolat. [2003. november 27-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. május 16.).
  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