Harries – Wongův graf - Harries–Wong graph
| Harries – Wongův graf | |
|---|---|
 Graf Harries – Wong | |
| Vrcholy | 70 |
| Hrany | 105 |
| Poloměr | 6 |
| Průměr | 6 |
| Obvod | 10 |
| Automorfismy | 24 (S4 ) |
| 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 – Wongův graf je 3-pravidelný neorientovaný graf se 70 vrcholy a 105 hranami.[1]
Graf Harries-Wong 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]
Charakteristický polynom grafu Harries-Wong je
Dějiny
V roce 1972 publikoval A. T. Balaban graf s klecí (3–10), 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 graf Harries-Wong.[6] Kromě toho jsou grafy Harries – Wong a Harriesův graf cospectral graphs.
Galerie
Chromatické číslo grafu Harries – Wong je 2.
Chromatický index grafu Harries – Wong je 3.
Alternativní kresba grafu Harries – Wong.
8 oběžných drah grafu Harries – Wong.
Reference
- ^ Weisstein, Eric W. „Graf Harries – Wong“. 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, USA Teorie grafů s aplikacemi. New York: Severní Holandsko, str. 237, 1976.