Holtův graf - Holt graph
| Holtův graf | |
|---|---|
 V Holtově grafu jsou všechny vrcholy ekvivalentní a všechny hrany jsou ekvivalentní, ale hrany nejsou ekvivalentní jejich inverzím. | |
| Pojmenoval podle | Derek F. Holt |
| Vrcholy | 27 |
| Hrany | 54 |
| Poloměr | 3 |
| Průměr | 3 |
| Obvod | 5 |
| Automorfismy | 54 |
| Chromatické číslo | 3 |
| Chromatický index | 5 |
| Tloušťka knihy | 3 |
| Číslo fronty | 3 |
| Vlastnosti | Vrchol-tranzitivní Edge-tranzitivní Napůl tranzitivní Hamiltonian Eulerian Cayleyův graf |
| Tabulka grafů a parametrů | |
V matematický pole teorie grafů, Holtův graf nebo Doyleův graf je nejmenší napůl tranzitivní graf, tj. nejmenší příklad a vrchol-tranzitivní a hrana tranzitivní graf, který také není symetrický.[1][2] Takové grafy nejsou běžné.[3] Je pojmenována podle Petera G. Doyla a Dereka F. Holta, kteří objevili stejný graf nezávisle v roce 1976[4] a 1981[5] resp.
Holtův graf má průměr 3, poloměr 3 a obvod 5, chromatické číslo 3, chromatický index 5 a je Hamiltonian s 98 472 odlišnými hamiltonovskými cykly.[6] Je to také 4-připojen k vrcholu a 4-připojeno k okraji graf. Má to tloušťka knihy 3 a číslo fronty 3.[7]
Má automorfická skupina objednávky 54 automorfismů.[6] Toto je menší skupina, než by měl symetrický graf se stejným počtem vrcholů a hran. Graf kresby vpravo to zdůrazňuje, protože postrádá reflexní symetrii.
Charakteristický polynom Holtova grafu je
Galerie
The chromatické číslo Holtova grafu je 3.
The chromatický index Holtova grafu je 5.
Holtův graf je Hamiltonian.
Reference
- ^ Doyle, P. "Graf 27 vertexů, který je veritní a tranzitivní, ale ne L-tranzitivní." Říjen 1998. [1]
- ^ Alspachu, Briane; Marušič, Dragan; Nowitz, Lewis (1994), "Vytváření grafů, které jsou ½-tranzitivní", Journal of the Australian Mathematical Society Series A, 56 (3): 391–402, doi:10.1017 / S1446788700035564, archivovány z originál dne 27. 11. 2003.
- ^ Jonathan L. Gross, Jay Yellen, Příručka teorie grafů, CRC Press, 2004, ISBN 1-58488-090-2, str. 491.
- ^ Doyle, P. G. (1976), Na přechodných grafech, Vedoucí práce, Harvard College. Jak uvádí MathWorld.
- ^ Holt, Derek F. (1981), „Graf, který je přechodný od hrany, ale nikoli obloukový“, Journal of Graph Theory, 5 (2): 201–204, doi:10,1002 / jgt.3190050210.
- ^ A b Weisstein, Eric W. „Doyle Graph“. MathWorld.
- ^ Jessica Wolz, Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018