Holt grófja
| Holt grófja | |
|---|---|
| A Holt-gráfban minden csúcs ekvivalens és minden él ekvivalens, de nincs olyan automorfizmus, amely a csúcsok permutációjával leképezne egy élt önmagára | |
| Valaki után elnevezve | Derek F. Holt |
| Csúcsok | 27 |
| borda | 54 |
| Sugár | 3 |
| Átmérő | 3 |
| Heveder | 5 |
| Automorfizmusok | 54 |
| Kromatikus szám | 3 |
| Kromatikus index | 5 |
| Tulajdonságok |
csúcs-tranzitív él-tranzitív féltranzitív Hamiltoni Euler Cayley gráf |
| Médiafájlok a Wikimedia Commons oldalon | |
A Holt -gráf vagy Doyle-gráf a legkisebb félig tranzitív gráf , azaz a legkisebb példa egy csúcstranzitív és éltranzitív gráfra, amely nem szimmetrikus [1] [2] . Ilyen grafikonokat nem gyakran találunk [3] . A gráf nevét Peter J. Doyle-ról és Derek F. Holtról kapta, akik egymástól függetlenül fedezték fel a gráfot 1976-ban [4] , illetve 1981-ben [5] .
A Holt-gráf átmérője 3, sugara 3 és kerülete 5, kromatikus száma 3, kromatikus indexe 5. A gráf Hamilton -féle, 98 472 különböző Hamilton-ciklussal [6] . A gráf 4 csúcshoz és 4 élhez kapcsolódik . 3 - as könyvbeágyazással és 3-as sorszámmal rendelkezik . [7]
A gráfnak van egy 54-es rendű automorfizmuscsoportja [6] . Ez a legkisebb csoport az azonos számú csúcsot és élt tartalmazó szimmetrikus gráfokhoz. A jobb oldali grafikon rajza hangsúlyozza a grafikon tükörszimmetriájának hiányát.
A gráf karakterisztikus polinomja az
Galéria
-
Holt gróf kromatikus száma 3.
-
A Holt-gráf kromatikus indexe 5.
-
A Holt-gráf Hamilton -féle .
Jegyzetek
- ↑ Doyle, 1985 .
- ↑ Alspach, Marušič, Nowitz, 1994 , p. 391–402.
- ↑ Gross, Yellen, 2004 , p. 491.
- ↑ Doyle, 1976 .
- ↑ Holt, 1981 , p. 201–204.
- ↑ 1 2 Weisstein, Eric W. Doyle Graph (angol) a Wolfram MathWorld webhelyen .
- ↑ Jessica Wolz, Lineáris elrendezések tervezése SAT segítségével . Mesterdolgozat, Tübingeni Egyetem, 2018
Irodalom
- Peter G. Doyle. Egy 27 csúcsos grafikon, amely csúcs-tranzitív és él-tranzitív, de nem L-tranzitív. - 1985. - október. - arXiv : math/0703861 .
- Brian Alspach, Dragan Marusic, Lewis Nowitz. ½-es tranzitív grafikonok készítése // Journal of the Australian Mathematical Society (A sorozat). - 1994. - T. 56 , sz. 3 . - doi : 10.1017/S1446788700035564 . Az eredetiből archiválva : 2003. november 27.
- Jonathan L. Gross, Jay Yellen. A gráfelmélet kézikönyve. - CRC Press, 2004. - ISBN 1-58488-090-2 .
- Doyle PG a tranzitív grafikonokon. - Harvard College, 1976. - (Senior szakdolgozat).
- Derek F. Holt. Egy gráf, amely éltranzitív, de nem ívtranzitív // Journal of Graph Theory . - 1981. - V. 5 , sz. 2 . - doi : 10.1002/jgt.3190050210 .
- Jessica Walz. Lineáris elrendezések tervezése SAT segítségével. - Tübingeni Egyetem, 2018. - (Mesterdolgozat).