Hamiltonian properties of polyhedra with few 3-cuts. A survey. (English) Zbl 1392.05066

Ozeki, Kenta; van Cleemput, Nico; Zamfirescu, Carol T.

Discrete Math. 341, No. 9, 2646-2660 (2018).

Summary: We give an overview of the most important techniques and results concerning the Hamiltonian properties of planar 3-connected graphs with few 3-vertex-cuts. In this context, we also discuss planar triangulations and their decomposition trees. We observe an astonishing similarity between the Hamiltonian behavior of planar triangulations and planar 3-connected graphs. In addition to surveying, (i) we give a unified approach to constructing non-traceable, non-Hamiltonian, and non-Hamiltonian-connected triangulations, and show that planar 3-connected graphs (ii) with at most one 3-vertex-cut are Hamiltonian-connected, and (iii) with at most two 3-vertex-cuts are 1-Hamiltonian, filling two gaps in the literature. Finally, we discuss open problems and conjectures.

MSC:

05C45	Eulerian and Hamiltonian graphs
05C10	Planar graphs; geometric and topological aspects of graph theory
05C40	Connectivity

Keywords:

planar graph; 3-connected graph; polyhedron; triangulation; decomposition tree; Hamiltonian; traceable; Hamiltonian-connected

References:

[1]	Akhmedova, A.; Winter, M., Chordal and timbral morphologies using Hamiltonian cycles, J. Math. Music, 8, 1, 1-24, (2014) · Zbl 1327.00014
[2]	Aldred, R. E.L.; Bau, S.; Holton, D. A.; McKay, B. D., Cycles through 23 vertices in 3-connected cubic planar graphs, Graphs Combin., 15, 373-376, (1999) · Zbl 0957.05064
[3]	Aldred, R. E.L.; Bau, S.; Holton, D. A.; McKay, B. D., Nonhamiltonian 3-connected cubic planar graphs, SIAM J. Discrete Math., 13, 25-32, (2000) · Zbl 0941.05041
[4]	Asano, T.; Kikuchi, S.; Saito, N., A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs, Discrete Appl. Math., 7, 1, 1-15, (1984) · Zbl 0531.68008
[5]	Bae, M. M.; Bose, B., Edge disjoint Hamiltonian cycles in \(k\)-ary \(n\)-cubes and hypercubes, IEEE Trans. Comput., 52, 10, 1271-1284, (2003)
[6]	Biggs, N.; Lloyd, E. K.; Wilson, R. J., Graph theory, 1736-1936, (1976), Clarendon Press
[7]	Böhme, T.; Harant, J., On Hamiltonian cycles in 4- and 5-connected plane triangulations, Discrete Math., 191, 25-30, (1998) · Zbl 0958.05085
[8]	Böhme, T.; Harant, J.; Tkáč, M., On the minimal number of separating 3-cycles in non-Hamiltonian maximal planar graphs, Tatra Mt. Math. Publ., 9, 97-102, (1996) · Zbl 0857.05065
[9]	Böhme, T.; Harant, J.; Tkáč, M., On certain Hamiltonian cycles in planar graphs, J. Graph Theory, 32, 81-96, (1999) · Zbl 0931.05047
[10]	Brinkmann, G.; Souffriau, J.; Van Cleemput, N., On the strongest form of a theorem of Whitney for Hamiltonian cycles in plane triangulations, J. Graph Theory, 83, 1, 78-91, (2016) · Zbl 1346.05149
[11]	Brinkmann, G.; Souffriau, J.; Van Cleemput, N., On the number of Hamiltonian cycles in triangulations with few separating triangles, J. Graph Theory, 87, 2, 164-175, (2018) · Zbl 1380.05119
[12]	G. Brinkmann, C.T. Zamfirescu, Polyhedra with few 3-cuts are Hamiltonian, submitted for publication. arXiv:1606.01693 [math.CO]. · Zbl 1409.05122
[13]	Chen, C., Any maximal planar graph with only one separating triangle is Hamiltonian, J. Comb. Optim., 7, 79-86, (2003) · Zbl 1046.90072
[14]	Chen, G.; Fan, G.; Yu, X., Cycles in 4-connected planar graphs, European J. Combin., 25, 763-780, (2004) · Zbl 1050.05032
[15]	Chiba, N.; Nishizeki, T., A theorem on paths in planar graphs, J. Graph Theory, 10, 449-450, (1986) · Zbl 0608.05048
[16]	Chiba, N.; Nishizeki, T., The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs, J. Algorithms, 10, 187-211, (1989) · Zbl 0689.68089
[17]	Chvátal, V., Tough graphs and Hamiltonian circuits, Discrete Math., 5, 3, 215-228, (1973) · Zbl 0256.05122
[18]	Cui, Q.; Hu, Y.; Wang, J., Long cycles in 4-connected planar graphs, Discrete Math., 309, 1051-1059, (2009) · Zbl 1170.05316
[19]	Cunningham, W. H.; Edmonds, J., A combinatorial decomposition theory, Canad. J. Math., 32, 734-765, (1980) · Zbl 0442.05054
[20]	Dillencourt, M. B., Hamiltonian cycles in planar triangulations with no separating triangles, J. Graph Theory, 14, 1, 31-49, (1990) · Zbl 0688.05052
[21]	Ellingham, M. N., Spanning paths, cycles and walks for graphs on surfaces, Congr. Numer., 115, 55-90, (1996) · Zbl 0894.05033
[22]	L. Euler, Solution d’une question curieuse qui ne paroit soumise à aucune analyse, in: Mémoires de l’Académie Royale des Sciences et Belles Lettres, Année 1759, vol. 15, Berlin, 1766, pp. 310-337. Entry E309 in the Euler Archive.
[23]	Faulkner, G. B.; Younger, D. H., Non-Hamiltonian cubic planar maps, Discrete Math., 7, 1, 67-74, (1974) · Zbl 0271.05106
[24]	Gao, Z.; Richter, R. B.; Yu, X., 2-walks in 3-connected planar graphs, Australas. J. Combin., 11, 117-122, (1995) · Zbl 0837.05050
[25]	Gao, Z.; Richter, R. B.; Yu, X., Erratum to: 2-walks in 3-connected planar graphs, Australas. J. Combin., 36, 315-316, (2006) · Zbl 1104.05021
[26]	Gardner, M., Mathematical games: about the remarkable similarity between the Icosian game and the towers of Hanoi, Sci. Am., 196, 150-156, (1957)
[27]	Garey, M. R.; Johnson, D. S.; Tarjan, R. E., The planar Hamiltonian circuit problem is NP-complete, SIAM J. Comput., 5, 704-714, (1976) · Zbl 0346.05110
[28]	Grünbaum, B., Convex polytopes, (1967), Wiley Interscience · Zbl 0163.16603
[29]	Grünbaum, B., Polytopes, graphs, and complexes, Bull. Amer. Math. Soc., 76, 1131-1201, (1970) · Zbl 0211.25001
[30]	Hakimi, S. L.; Schmeichel, E. F.; Thomassen, C., On the number of Hamiltonian cycles in a maximal planar graph, J. Graph Theory, 3, 365-370, (1979) · Zbl 0422.05050
[31]	Harant, J.; Owens, P. J., Non-Hamiltonian \(\frac{5}{4}\)-tough maximal planar graphs, Discrete Math., 147, 301-305, (1995) · Zbl 0838.05043
[32]	G. Helden, Errata concerning [33], Available at http://publications.rwth-aachen.de/record/62349/files/.
[33]	Helden, G., Hamiltonicity of maximal planar graphs and planar triangulations, (2007), RWTH Aachen Germany, (Ph.D. thesis)
[34]	Helden, G., Each maximal planar graph with exactly two separating triangles is Hamiltonian, Discrete Appl. Math., 155, 1833-1836, (2007) · Zbl 1123.05059
[35]	Helden, G.; Vieten, O., Hamilton cycles in maximal planar graphs, Electron. Notes Discrete Math., 25, 71, (2006) · Zbl 1134.05325
[36]	Hendry, G. R.T., Scattering number and extremal non-Hamiltonian graphs, Discrete Math., 71, 2, 165-175, (1988) · Zbl 0655.05044
[37]	Holton, D. A.; McKay, B. D., The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices, J. Combin. Theory Ser. B, 45, 3, 305-319, (1988) · Zbl 0607.05051
[38]	Hsu, L.-H.; Lin, C.-K., Optimal \(k\)-fault-tolerant Hamiltonian graphs, (Graph Theory and Interconnection Networks, (2008), CRC Press), (Chapter 11)
[39]	Jackson, B.; Whitehead, C. A., Some remarks on jaeger’s dual-Hamiltonian conjecture, Ann. Inst. Fourier, 49, 3, 921-926, (1999) · Zbl 0920.05048
[40]	Jackson, B.; Yu, X., Hamilton cycles in plane triangulations, J. Graph Theory, 41, 2, 138-150, (2002) · Zbl 1012.05106
[41]	Jung, H. A., On a class of posets and the corresponding comparability graphs, J. Combin. Theory Ser. B, 24, 2, 125-133, (1978) · Zbl 0382.05045
[42]	Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations, (1972), Plenum Press New York), 85-103
[43]	Kawarabayashi, K.; Ozeki, K., 5-connected toroidal graphs are Hamiltonian-connected, SIAM J. Discrete Math., 30, 1, 112-140, (2016) · Zbl 1329.05180
[44]	Kirkman, T. P., On the representation of polyedra, Phil. Trans. Royal Soc. London, 146, 413-418, (1856)
[45]	Kužel, R.; Ryjáček, Z.; Vrána, P., Thomassen’s conjecture implies polynomiality of 1-Hamilton-connectedness in line graphs, J. Graph Theory, 69, 3, 241-250, (2012) · Zbl 1242.05157
[46]	Laporte, G., The traveling salesman problem: an overview of exact and approximate algorithms, European J. Oper. Res., 59, 231-247, (1992) · Zbl 0760.90089
[47]	Malkevitch, J., Polytopal graphs, (Selected Topics in Graph Theory, vol. 3, (1988), Academic Press New York), 169-188 · Zbl 0678.05015
[48]	Marušič, D., Hamilton cycles and paths in fullerenes, J. Chem. Inf. Model., 47, 732-736, (2007)
[49]	Moon, J. W.; Moser, L., Simple paths on polyhedra, Pacific J. Math., 13, 629-631, (1963) · Zbl 0115.41001
[50]	A. Nakamoto, T. Nozawa, K. Ozeki, Book embedding of graphs on the projective plane, submitted for publication. · Zbl 1335.05050
[51]	Nash-Williams, C. St. J.A., Unexplored and semi-explored territories in graph theory, (New Directions in the Theory of Graphs, (1973), Academic Press New York), 149-186 · Zbl 0263.05101
[52]	Nelson, D. A., Hamiltonian graphs, (1973), Vanderbilt University, (Master’s thesis)
[53]	Nishizeki, T., A 1-tough Nonhamiltonian maximal planar graph, Discrete Math., 30, 305-307, (1980) · Zbl 0442.05046
[54]	Owens, P. J., Non-Hamiltonian maximal planar graphs with high toughness, Tatra Mt. Math. Publ., 18, 89-103, (1999) · Zbl 0951.05067
[55]	Ozeki, K.; Vrána, P., 2-edge-Hamiltonian-connectedness of 4-connected plane graphs, European J. Combin., 35, 432-448, (2014), Selected Papers of EuroComb’11 · Zbl 1296.05116
[56]	K. Ozeki, C.T. Zamfirescu, Every 4-connected graph with crossing number 2 is Hamiltonian, submitted for publication. · Zbl 1401.05175
[57]	Ozeki, K.; Zamfirescu, C. T., Non-Hamiltonian triangulations with distant separating triangles, Discrete Math., 341, 7, 1900-1902, (2018) · Zbl 1387.05141
[58]	M.D. Plummer, Problem, in: A. Hajnal, R. Rado, V.T. Sos (Eds.), Infinite and Finite Sets, Colloq. Math. Soc. J. Bolyai 10, vol. III, North-Holland, Amsterdam, 1975, pp. 1549-1550.
[59]	Sanders, D. P., On paths in planar graphs, J. Graph Theory, 24, 4, 341-345, (1997) · Zbl 0880.05059
[60]	A. Schmid, J.M. Schmidt, Computing 2-walks in polynomial time, in: E.W. Mayr, N. Ollinger (Eds.), 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, in: Leibniz International Proceedings in Informatics, LIPIcs, vol. 30, 2015, pp. 676-688. · Zbl 1355.68129
[61]	E. Steinitz, Polyeder und Raumeinteilungen, in: Encyclopädie der mathematischen Wissenschaften, Band 3 (Geometrie), (Part 3AB12) 1922, pp. 1-139.
[62]	P.G. Tait, Listing’s Topologie. Phil. Mag. (5th ser.), vol. 17, 1884, pp. 30-46. Reprinted in: Scientific Papers of P.G. Tait, vol. II, pp. 85-98.
[63]	F. Takeo, On triangulated graphs I, Bull. Fukuoka Gakugei Univ. III, vol. 10, 1960, pp. 9-21.
[64]	Thomas, R.; Yu, X., 4-connected projective-planar graphs are Hamiltonian, J. Combin. Theory Ser. B, 62, 1, 114-132, (1994) · Zbl 0802.05051
[65]	Thomassen, C., Planar and infinite Hypohamiltonian and hypotraceable graphs, Discrete Math., 14, 4, 377-389, (1976) · Zbl 0322.05130
[66]	Thomassen, C., Theory and applications of graphs: Proceedings, michigan, 1976, 557-571, (1978), Springer, Berlin, Heidelberg, (Chapter “Hypohamiltonian graphs and digraphs”)
[67]	Thomassen, C., Planar cubic Hypohamiltonian and hypotraceable graphs, J. Combin. Theory Ser. B, 30, 36-44, (1981) · Zbl 0388.05033
[68]	Thomassen, C., A theorem on paths in planar graphs, J. Graph Theory, 7, 2, 169-176, (1983) · Zbl 0515.05040
[69]	Tutte, W. T., On Hamiltonian circuits, J. Lond. Math. Soc., 21, 2, 98-101, (1946) · Zbl 0061.41306
[70]	Tutte, W. T., A theorem on planar graphs, Trans. Amer. Math. Soc., 82, 99-116, (1956) · Zbl 0070.18403
[71]	Tutte, W. T., Bridges and Hamiltonian circuits in planar graphs, Aequationes Math., 15, 1, 1-33, (1977) · Zbl 0357.05039
[72]	N. Van Cleemput, Hamiltonian-connectedness of triangulations with few separating triangles, Contrib. Discrete Math., in press. arXiv:1605.01231 [math.CO].
[73]	Whitney, H., A theorem on graphs, Ann. of Math., 32, 2, 378-390, (1931) · JFM 57.0727.03
[74]	Whitney, H., 2-isomorphic graphs, Amer. J. Math., 55, 1-4, 245-254, (1933) · JFM 59.1235.01
[75]	C.T. Zamfirescu, Cubic vertices in planar hypohamiltonian graphs, submitted for publication.