×

zbMATH — the first resource for mathematics

5-connected toroidal graphs are Hamiltonian-connected. (English) Zbl 1329.05180

MSC:
05C45 Eulerian and Hamiltonian graphs
05C40 Connectivity
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] N. Chiba and T. Nishizeki, A theorem on paths in planar graphs, J. Graph Theory, 10 (1986), pp. 449–450. · Zbl 0608.05048
[2] N. Chiba and T. Nishizeki, The Hamiltonian cycle problem is linear-time solvable for \(4\)-connected planar graphs, J. Algorithms, 10 (1989), pp. 187–211. · Zbl 0689.68089
[3] N. Dean, R. J. Gould, and T. E. Lindquester, On a generalization of Ore’s theorem for Hamiltonian-connected graphs, in 21st Southeastern Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, 1990, pp. 207–215. · Zbl 0862.05077
[4] B. Grünbaum, Polytopes, graphs, and complexes, Bull. Amer. Math. Soc., 76 (1970), pp. 1131–1201.
[5] K. Kawarabayashi and K. Ozeki, Hamiltonian Cycles in 4-Connected Triangulations on Torus, preprint. · Zbl 1274.05281
[6] K. Kawarabayashi and K. Ozeki, 4-connected projective-planar graphs are Hamiltonian-connected, J. Combin. Theory Ser., 112 (2015), pp. 36–69. · Zbl 1310.05132
[7] P. N. Klein, A linear time approximation scheme for TSP for planar wieghted graphs, in Proceedings of the 46th Symposium on Foundations of Computer Science, 2005, pp. 146–155.
[8] B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins University Press, Baltimore, 2001. · Zbl 0979.05002
[9] J. W. Moon and L. Moser, Simple paths on polyhedra, Pacific J. Math., 13 (1963), pp. 629–631. · Zbl 0115.41001
[10] C. St.J. A. Nash-Williams, Unexplored and semi-explored territories in graph theory, in New Directions in the Theory of Graphs, Academic Press, New York, 1973, pp. 149–186. · Zbl 0263.05101
[11] D. Sanders, On paths in planar graphs, J. Graph Theory, 24 (1997), pp. 341–345. · Zbl 0880.05059
[12] R. Thomas and X. Yu, \(4\)-connected projective-planar graphs are Hamiltonian, J. Combin. Theory Ser. B, 62 (1994), pp. 114–132. · Zbl 0802.05051
[13] R. Thomas and X. Yu, Five-connected toroidal graphs are Hamiltonian, J. Combin. Theory Ser. B, 69 (1997), pp. 79–96. · Zbl 0867.05043
[14] R. Thomas, X. Yu, and W. Zang, Hamilton paths in toroidal graphs, J. Combin. Theory Ser. B, 94 (2005), pp. 214–236. · Zbl 1066.05082
[15] C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory, 7 (1983), pp. 169–176. · Zbl 0515.05040
[16] W.T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc., 82 (1956), pp. 99–116. · Zbl 0070.18403
[17] W.T. Tutte, On Hamiltonian circuits, J. London Math. Soc., 2 (1946), pp. 98–101. · Zbl 0061.41306
[18] H. Whitney, A theorem on graphs, Ann. of Math., 32 (1931), pp. 378–390. · JFM 57.0727.03
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.