Ellingham – Hortonův graf - Ellingham–Horton graph
| Ellingham – Hortonovy grafy | |
|---|---|
 Ellingham – Horton 54-graf. | |
| Pojmenoval podle | Joseph Horton a Mark Ellingham |
| Vrcholy | 54 (54 grafů) 78 (78 grafů) |
| Hrany | 81 (54 grafů) 117 (78 grafů) |
| Poloměr | 9 (54 grafů) 7 (78 grafů) |
| Průměr | 10 (54 grafů) 13 (78 grafů) |
| Obvod | 6 (oba) |
| Automorfismy | 32 (54 grafů) 16 (78 grafů) |
| Chromatické číslo | 2 (oba) |
| Chromatický index | 3 (oba) |
| Tloušťka knihy | 3 (oba) |
| Číslo fronty | 2 (oba) |
| Vlastnosti | Krychlový (oba) Bipartitní (oba) Pravidelný (oba) |
| Tabulka grafů a parametrů | |
V matematický pole teorie grafů, Ellingham – Hortonovy grafy jsou dva 3-pravidelné grafy na vrcholech 54 a 78: the Ellingham – Horton 54 grafů a Ellingham – Horton 78 grafů.[1] Jsou pojmenovány po Josephu D. Hortonovi a Mark N. Ellingham, jejich objevitelé. Tyto dva grafy poskytují protiklady k domněnce W. T. Tutte že každý krychlový 3 připojené bipartitní graf je Hamiltonian.[2] The tloušťka knihy z Ellingham-Horton 54-graf a Ellingham-Horton 78-graf je 3 a čísla fronty 2.[3]
Prvním protipříkladem domněnky Tutte byl Hortonův graf, publikováno Bondy & Murty (1976).[4] Po Hortonově grafu byla nalezena řada menších protikladů k domněnce Tutte. Mezi nimi je 92-vertexový graf podle Horton (1982),[5] 78-vertexový graf podle Owens (1983),[6] a dva grafy Ellingham – Horton.
První graf Ellingham – Horton publikoval Ellingham (1981) a je objednávky 78.[7] V té době to byl nejmenší známý protiklad k domněnce Tutte. Druhý graf Ellingham – Horton publikoval Ellingham & Horton (1983) a je objednávky 54.[8] V roce 1989 byl objeven Georgesův graf, nejmenší v současné době známý ne-hamiltonovský 3-propojený kubický bipartitní graf, který obsahuje 50 vrcholů.[9]
Galerie
The chromatické číslo grafu Ellingham – Horton 54 je 2.
The chromatický index grafu Ellingham – Horton 54 je 3.
The chromatické číslo grafu Ellingham – Horton 78 je 2.
The chromatický index grafu Ellingham – Horton 78 je 3.
Reference
- ^ Weisstein, Eric W. „Tutte Conjecture“. MathWorld.
- ^ Tutte, W. T. (1971), „O 2-faktorech bikubických grafů“, Diskrétní matematika, 1 (2): 203–208, doi:10.1016 / 0012-365X (71) 90027-6.
- ^ Jessica Wolz, Engineering Linear Layouts with SAT. Diplomová práce, Universität Tübingen, 2018
- ^ Bondy, J. A.; Murty, USA (1976), Teorie grafů s aplikacemi, New York: Severní Holandsko, s.240, ISBN 0-444-19451-7
- ^ Horton, J. D. (1982), „O dvou faktorech bipartitních pravidelných grafů“, Diskrétní matematika, 41 (1): 35–41, doi:10.1016 / 0012-365X (82) 90079-6.
- ^ Owens, P. J. (1983), „Bipartitní kubické grafy a exponent krátkosti“, Diskrétní matematika, 44 (3): 327–330, doi:10.1016 / 0012-365X (83) 90201-7.
- ^ Ellingham, M. N. (1981), Non-Hamiltonian 3-spojené kubické partitové grafy, Research Report 28, Melbourne: Dept. of Math., Univ. Melbourne.
- ^ Ellingham, M. N .; Horton, J. D. (1983), „Non-Hamiltonovské 3-spojené kubické bipartitní grafy“, Journal of Combinatorial Theory, Series B, 34 (3): 350–353, doi:10.1016/0095-8956(83)90046-1.
- ^ Georges, J. P. (1989), „nehamiltonovské bikubické grafy“, Journal of Combinatorial Theory, Series B, 46 (1): 121–124, doi:10.1016/0095-8956(89)90012-9.