Regular non-hamiltonian polyhedral graphs

Nico Van Cleemput and Carol T. Zamfirescu

Applied Mathematics and Computation, 2018, vol. 338, issue C, 192-206

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.

Keywords: Non-hamiltonian; Non-traceable; Polyhedron; Planar; 3-connected; Regular graph (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S009630031830479X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:338:y:2018:i:c:p:192-206

DOI: 10.1016/j.amc.2018.05.062

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().