Back to Search
Start Over
Regular non-hamiltonian polyhedral graphs.
- Source :
-
Applied Mathematics & Computation . Dec2018, Vol. 338, p192-206. 15p. - Publication Year :
- 2018
-
Abstract
- Invoking Steinitz’ Theorem, in the following a polyhedron shall be a 3-connected planar graph. From around 1880 till 1946 Tait’s conjecture that cubic polyhedra are hamiltonian was thought to hold—its truth would have implied the Four Colour Theorem. However, Tutte gave a counterexample. We briefly survey the ensuing hunt for the smallest non-hamiltonian cubic polyhedron, the Lederberg-Bosák-Barnette graph, and prove that there exists a non-hamiltonian essentially 4-connected cubic polyhedron of order n if and only if n ≥ 42. This extends work of Aldred, Bau, Holton, and McKay. We then present our main results which revolve around the quartic case: combining a novel theoretical approach for determining non-hamiltonicity in (not necessarily planar) graphs of connectivity 3 with computational methods, we dramatically improve two bounds due to Zaks. In particular, we show that the smallest non-hamiltonian quartic polyhedron has at least 35 and at most 39 vertices, thereby almost reaching a quartic analogue of a famous result of Holton and McKay. As an application of our results, we obtain that the shortness coefficient of the family of all quartic polyhedra does not exceed 5/6. The paper ends with a discussion of the quintic case in which we tighten a result of Owens. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00963003
- Volume :
- 338
- Database :
- Academic Search Index
- Journal :
- Applied Mathematics & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 131294886
- Full Text :
- https://doi.org/10.1016/j.amc.2018.05.062