×

zbMATH — the first resource for mathematics

Hamiltonian properties of polyhedra with few 3-cuts. A survey. (English) Zbl 1392.05066
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
PDF BibTeX XML Cite
Full Text: DOI
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.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.