Regular non-Hamiltonian polyhedral graphs. (English) Zbl 1427.05126

Summary: 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\geq 42\). This extends work of R. E. L. Aldred et al. [SIAM J. Discrete Math. 13, No. 1, 25–32 (2000; Zbl 0941.05041)]. 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 J. Zaks [J. Comb. Theory, Ser. B 21, 116–131 (1976; Zbl 0309.05120)]. 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 D. A. Holton and B. D. McKay [ibid. 45, No. 3, 305–319 (1988; Zbl 0607.05051)]. 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.


05C45 Eulerian and Hamiltonian graphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
05C35 Extremal problems in graph theory
Full Text: DOI


[1] Aldred, R. E.L.; Bau, S.; Holton, D. A.; McKay, B. D., Nonhamiltonian 3-connected planar cubic graphs, SIAM J. Discrete Math., 13, 25-32 (2000) · Zbl 0941.05041
[2] Barnette, D. W.; Wegner, G., Hamiltonian circuits in simple 3-polytopes with up to 26 vertices, Israel J. Math., 19, 212-216 (1974) · Zbl 0302.05102
[3] Bekos, M. A.; Raftopoulou, C. N., On a conjecture of Lovász on circle-representations of simple 4-regular planar graphs, J. Comput. Geom., 6, 1-20 (2015) · Zbl 1405.05123
[4] Biggs, N. L.; Lloyd, E. K.; Wilson, R. J., Graph Theory 1736-1936 (1976), Clarendon Press: Clarendon Press Oxford · Zbl 0335.05101
[5] Bondy, J. A.; Häggkvist, R., Edge-disjoint hamilton cycles in 4-regular planar graphs, Aequat. Math., 22, 42-45 (1981) · Zbl 0464.05037
[6] Bosák, J., Decompositions of Graphs (1990), Taylor & Francis · Zbl 0701.05042
[7] Brinkmann, G.; Greenberg, S.; Greenhill, C.; McKay, B. D.; Thomas, R.; Wollan, P., Generation of simple quadrangulations of the sphere, Discrete Math., 305, 33-54 (2005) · Zbl 1078.05023
[8] Brinkmann, G.; McKay, B. D., Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem., 42, 909-924 (2007)
[9] Broersma, H. J.; Duijvestijn, A. J.W.; Göbel, F., Generating all 3-connected 4-regular planar graphs from the octahedron graph, J. Graph Theory, 17, 613-620 (1993) · Zbl 0781.05047
[10] Butler, J. W., Hamiltonian circuits on simple 3-polytopes, J. Combin. Theory Ser. B, 15, 69-73 (1973) · Zbl 0248.05103
[11] Chartrand, G.; Gould, R. J.; Kapoor, S. F., On homogeneously traceable nonhamiltonian graphs, Ann. N.Y. Acad. Sci., 319, 130-135 (1979) · Zbl 0481.05039
[12] Fleischner, H.; Jackson, B., A note concerning some conjectures on cyclically 4-edge connected 3-regular graphs, Ann. Discrete Math., 41, 171-177 (1988) · Zbl 0677.05054
[13] Grünbaum, B., Convex Polytopes (2003), Springer · Zbl 1024.52001
[14] Grünbaum, B.; Walther, H., Shortness exponents of families of graphs, J. Combin. Theory Ser. A, 14, 364-385 (1973) · Zbl 0263.05103
[15] Harant, J.; Owens, P. J.; Tkáč, M.; Walther, H., 5-regular 3-polytopal graphs with edges of only two types and shortness exponents less than one, Discrete Math., 150, 143-153 (1996) · Zbl 0852.05056
[16] Hasheminezhad, M.; McKay, B. D.; Reeves, T., Recursive generation of simple planar 5-regular graphs and pentangulations, J. Graph Alg. Appl., 15, 417-436 (2011) · Zbl 1276.05033
[17] High, D., On 4-regular planar hamiltonian graphs (2006), Western Kentucky University, M.Sc. thesis
[18] Hoffmann, T., Hamiltonsche Wege in planaren Graphen (1999), Universität Dortmund, Diploma thesis
[19] Holton, D. A.; McKay, B. D., The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices, J. Combin. Theory Ser. B, 45, 305-319 (1988) · Zbl 0607.05051
[20] Horton, J. D., A hypotraceable graph, Res. Rep. CORR, 73-74 (1973)
[21] Iwamoto, C.; Toussaint, G. T., Finding hamiltonian circuits in arrangements of Jordan curves is NP-complete, Inf. Proc. Lett., 52, 183-189 (1994) · Zbl 0823.68084
[22] King, R. B., Chemical applications of topology and group theory V: polyhedral metal clusters and boron hydrides, J. Am. Chem. Soc., 94, 95-103 (1972)
[23] Knorr, P., Aufspannende Kreise und Wege in polytopalen Graphen (2010), Universität Dortmund, Ph.D. thesis
[24] Lehel, J., Generating all 4-regular planar graphs from the graph of the octahedron, J. Graph Theory, 5, 423-426 (1981) · Zbl 0474.05058
[25] B.D. McKay, http://mathoverflow.net/questions/112661/spanning-trees-of-plane-graphs-containing-an-edge-of-every-face; B.D. McKay, http://mathoverflow.net/questions/112661/spanning-trees-of-plane-graphs-containing-an-edge-of-every-face
[26] B.D. McKay, http://users.cecs.anu.edu.au/ bdm/data/planegraphs.html; B.D. McKay, http://users.cecs.anu.edu.au/ bdm/data/planegraphs.html
[27] Neyt, A., Platypus graphs: structure and generation (2017), Ghent University, M.Sc. thesis
[28] Okamura, H., Every simple 3-polytope of order 32 or less is hamiltonian, J. Graph Theory, 6, 185-196 (1982) · Zbl 0493.05043
[29] Owens, P. J., On regular graphs and hamiltonian circuits, including answers to some questions of Joseph Zaks, J. Combin. Theory Ser. B, 28, 262-277 (1980) · Zbl 0438.05042
[30] Owens, P. J., Regular planar graphs with faces of only two types and shortness parameters, J. Graph Theory, 8, 253-275 (1984) · Zbl 0541.05037
[31] Owens, P. J., Shortness parameters for polyhedral graphs, Discrete Math., 206, 159-169 (1999) · Zbl 0932.05047
[32] K. Ozeki, N. Van Cleemput, C.T. Zamfirescu, Hamiltonian properties of polyhedra with few 3-cuts-a survey, to appear in: Discrete Math. (2018).; K. Ozeki, N. Van Cleemput, C.T. Zamfirescu, Hamiltonian properties of polyhedra with few 3-cuts-a survey, to appear in: Discrete Math. (2018). · Zbl 1392.05066
[33] Sachs, H., Construction of non-hamiltonian planar regular graphs of degrees 3, 4 and 5 with highest possible connectivity, Proceedings of the Theory of Graphs International Symposium Rome, 373-382 (1967), Dunod: Dunod Paris · Zbl 0202.23403
[34] Steinitz, E., Polyeder und Raumeinteilungen, (Meyer, W. F.; Mohrmann, H., Encyklopädie der mathematischen Wissenschaften (1922), Teubner: Teubner Leipzig), 1-139
[35] Tait, P. G., Listing’s Topologie, Philos. Mag. (5th Series), 17, 30-46 (1884)
[36] Thomassen, C., Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Math., 14, 377-389 (1976) · Zbl 0322.05130
[37] Thomassen, C., Planar cubic hypohamiltonian and hypotraceable graphs, J. Combin. Theory Ser. B, 30, 36-44 (1981) · Zbl 0388.05033
[38] Tutte, W. T., On Hamiltonian circuits, J. Lond. Math. Soc., 21, 98-101 (1946) · Zbl 0061.41306
[39] Tutte, W. T., A theorem on planar graphs, Trans. Amer. Math. Soc., 82, 99-116 (1956) · Zbl 0070.18403
[40] Tutte, W. T., A non-hamiltonian planar graph, Acta Math. Hungar., 11, 371-375 (1960) · Zbl 0103.16202
[41] Walther, H., Über das Problem der Existenz von Hamiltonkreisen in planaren, regulären Graphen, Math. Nachr., 39, 277-296 (1969) · Zbl 0169.26401
[42] Walther, H., A non-hamiltonian five-regular multitriangular polyhedral graph, Discrete Math., 150, 387-392 (1996) · Zbl 0854.05065
[43] Zaks, J., Pairs of hamiltonian circuits in 5-connected planar graphs, J. Combin. Theory Ser. B, 21, 116-131 (1976) · Zbl 0309.05120
[44] Zamfirescu, T., Three small cubic graphs with interesting hamiltonian properties, J. Graph Theory, 4, 287-292 (1980) · Zbl 0442.05047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.