Name
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.amc.2018.05.062 | Applied Mathematics and Computation |
Keywords | Field | DocType |
Non-hamiltonian,Non-traceable,Polyhedron,Planar,3-connected,Regular graph | Quintic function,Combinatorics,Vertex (geometry),Mathematical analysis,Polyhedron,Regular graph,Quartic function,Counterexample,Conjecture,Mathematics,Planar graph | Journal |
Volume | ISSN | Citations |
338 | 0096-3003 | 0 |
PageRank | References | Authors |
0.34 | 15 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nico Van Cleemput | 1 | 16 | 6.31 |
| Carol T. Zamfirescu | 2 | 38 | 15.25 |