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

Van Cleemput, Nicolas; Zamfirescu, Carol T.

Appl. Math. Comput. 338, 192-206 (2018).

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.

MSC:

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

Keywords:

non-Hamiltonian graph; non-traceable graph; polyhedron; planar graph; 3-connected graph; regular graph

Citations:

Zbl 0941.05041; Zbl 0309.05120; Zbl 0607.05051

Software:

MathOverflow; plantri

References:

[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 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)
[13]	Grünbaum, B., Convex polytopes, (2003), Springer
[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.
[26]	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). · 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 Paris · Zbl 0202.23403
[34]	Steinitz, E., Polyeder und raumeinteilungen, (Meyer, W. F.; Mohrmann, H., Encyklopädie der mathematischen Wissenschaften, (1922), Teubner Leipzig), 1-139
[35]	Tait, P. G., Listing’s {\it topologie}, Philos. Mag. (5th Series), 17, 30-46, (1884) · JFM 16.0468.03
[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