Harriesův graf - Harries graph
| Harriesův graf | |
|---|---|
 Harriesův graf | |
| Vrcholy | 70 |
| Hrany | 105 |
| Poloměr | 6 |
| Průměr | 6 |
| Obvod | 10 |
| Automorfismy | 120 (S5 ) |
| Chromatické číslo | 2 |
| Chromatický index | 3 |
| Tloušťka knihy | 3 |
| Číslo fronty | 2 |
| Vlastnosti | Krychlový Klec Bez trojúhelníků Hamiltonian |
| Tabulka grafů a parametrů | |
V matematický pole teorie grafů, Harriesův graf nebo Klec Harries (3-10) je 3-pravidelný neorientovaný graf se 70 vrcholy a 105 hranami.[1]
Harriesův graf má chromatické číslo 2, chromatický index 3, poloměr 6, průměr 6, obvod 10 a je Hamiltonian. Je to také 3-připojen k vrcholu a 3-připojeno k okraji nerovinný kubický graf. Má to tloušťka knihy 3 a číslo fronty 2.[2]
The charakteristický polynom Harriesova grafu je
Dějiny
V roce 1972 publikoval A. T. Balaban (3-10) -klecový graf, kubický graf, který má pro obvod 10 co nejméně vrcholů.[3] Byla to první objevená (3-10) klec, ale nebyla jedinečná.[4]
Úplný seznam (3-10) klecí a důkaz minimality podali O'Keefe a Wong v roce 1980.[5] Existují tři odlišné grafy (3–10) klecí - graf Balaban 10-klec, Harriesův graf a Harries – Wongův graf.[6] Kromě toho jsou grafy Harries – Wong a Harriesův graf cospectral graphs.
Galerie
Chromatické číslo Harriesova grafu je 2.
Chromatický index Harriesova grafu je 3.
Alternativní kresba Harriesova grafu.
Alternativní kresba zdůrazňující 4 oběžné dráhy grafu.
Reference
- ^ Weisstein, Eric W. „Harriesův graf“. MathWorld.
- ^ Jessica Wolz, Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018
- ^ A. T. Balaban, Trojmocný graf obvodu deset, J. Combin. Theory Ser. B 12, 1-5. 1972.
- ^ Pisanski, T .; Boben, M .; Marušič, D .; a Orbanić, A. „Zobecněné konfigurace Balabanu.“ Předtisk. 2001. [1].
- ^ M. O'Keefe a P.K. Wong, Nejmenší graf obvodu 10 a valence 3, J. Combin. Theory Ser. B 29 (1980) 91-105.
- ^ Bondy, J. A. a Murty, U. S. R. Teorie grafů s aplikacemi. New York: Severní Holandsko, str. 237, 1976.