Contele de Holt
| Contele de Holt | |
|---|---|
| Într-un grafic Holt, toate vârfurile sunt echivalente și toate muchiile sunt echivalente, dar nu există un automorfism care mapează o muchie la sine cu permutarea nodurilor | |
| Numit după | Derek F. Holt |
| Vârfurile | 27 |
| coaste | 54 |
| Rază | 3 |
| Diametru | 3 |
| Circumferinţă | 5 |
| Automorfisme | 54 |
| Număr cromatic | 3 |
| Indicele cromatic | 5 |
| Proprietăți |
varf-tranzitiv muchie-tranzitiv semi -tranzitiv Hamiltonian Euler Cayley graph |
| Fișiere media la Wikimedia Commons | |
Graficul Holt sau graficul Doyle este cel mai mic graf semi-tranzitiv , adică cel mai mic exemplu de graf tranzitiv de vârf și tranzitiv de muchie care nu este simetric [1] [2] . Asemenea grafice nu se găsesc des [3] . Graficul este numit după Peter J. Doyle și Derek F. Holt, care au descoperit în mod independent graficul în 1976 [4] și, respectiv, 1981 [5] .
Graficul Holt are diametrul 3, raza 3 și circumferința 5, numărul cromatic 3, indicele cromatic 5. Graficul este hamiltonian cu 98.472 de cicluri hamiltoniene diferite [6] . Graficul este conectat cu 4 vârfuri și conectat cu 4 muchii . Are o încorporare de carte de 3 și un număr de coadă de 3. [7]
Graficul are un grup de automorfism de ordinul 54 [6] . Acesta este cel mai mic grup pentru graficele simetrice cu același număr de vârfuri și muchii. Desenul graficului din dreapta subliniază lipsa de simetrie în oglindă a graficului.
Polinomul caracteristic al graficului este
Galerie
-
Numărul cromatic al contelui Holt este 3.
-
Indicele cromatic al graficului Holt este 5.
-
Graficul Holt este hamiltonian .
Note
- ↑ 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 (engleză) pe site-ul Wolfram MathWorld .
- ↑ Jessica Wolz, Engineering Linear Layouts with SAT . Teză de master, Universitatea din Tübingen, 2018
Literatură
- Peter G. Doyle. Un grafic cu 27 de vârfuri care este tranzitiv la vârf și tranzitiv la margine, dar nu L-tranzitiv. - 1985. - Octombrie. - arXiv : math/0703861 .
- Brian Alspach, Dragan Marusic, Lewis Nowitz. Construirea de grafice care sunt ½-tranzitive // Journal of the Australian Mathematical Society (Seria A). - 1994. - T. 56 , nr. 3 . - doi : 10.1017/S1446788700035564 . Arhivat din original pe 27 noiembrie 2003.
- Jonathan L. Gross, Jay Yellen. Manual de teorie a grafurilor. - CRC Press, 2004. - ISBN 1-58488-090-2 .
- Doyle PG despre graficele tranzitive. - Harvard College, 1976. - (Teză de studii superioare).
- Derek F. Holt. Un grafic care este tranzitiv la margine, dar nu este tranzitiv în arc // Journal of Graph Theory . - 1981. - V. 5 , nr. 2 . - doi : 10.1002/jgt.3190050210 .
- Jessica Walz. Proiectări liniare cu SAT. - Universitatea din Tübingen, 2018. - (Teză de master).