×

zbMATH — the first resource for mathematics

Hamilton paths in toroidal graphs. (English) Zbl 1066.05082
Summary: W. T. Tutte [Trans. Am. Math. Soc. 82, 99–11 (1956; Zbl 0070.18403)] has shown that every 4-connected planar graph contains a Hamilton cycle. B. Grünbaum [Bull. Am. Math. Soc. 76, 1131–1201 (1970; Zbl 0211.25001)] and C. St. J. A. Nash-Williams [New Direct. Theory Graphs, Proc. third Ann Arbor Conf., Univ. Michigan 1971, 149–186 (1973; Zbl 0263.05101)] independently conjectured that the same is true for toroidal graphs. In this paper, we prove that every 4-connected toroidal graph contains a Hamilton path.
Reviewer: Reviewer (Berlin)

MSC:
05C45 Eulerian and Hamiltonian graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Altshuler, A., Hamiltonian circuits in some maps on the torus, Discrete math., 1, 299-314, (1972) · Zbl 0226.05109
[2] Brunet, R.; Richter, R.B., Hamiltonicity of 5-connected toroidal triangulations, J. graph theory, 20, 267-286, (1995) · Zbl 0841.05061
[3] Grünbaum, B., Polytopes, graphs, and complexes, Bull. amer. math. soc., 76, 1131-1201, (1970) · Zbl 0211.25001
[4] C.St.J.A. Nash-Williams, Unexplored and semi-explored territories in graph theory, in: F. Harary (Ed.), New Directions in Graph Theory, Academic Press, New York, 1973, pp. 169-176. · Zbl 0263.05101
[5] Thomas, R.; Yu, X., 4-connected projective-planar graphs are Hamiltonian, J. combin. theory, ser. B, 62, 114-132, (1994) · Zbl 0802.05051
[6] Thomas, R.; Yu, X., 5-connected toroidal graphs are Hamiltonian, J. combin. theory, ser. B, 69, 79-96, (1997) · Zbl 0867.05043
[7] Thomassen, C., A theorem on paths in planar graphs, J. graph theory, 7, 169-176, (1983) · Zbl 0515.05040
[8] Tutte, W.T., A theorem on planar graphs, Trans. amer. math. soc., 82, 99-116, (1956) · Zbl 0070.18403
[9] Whitney, H., A theorem on graphs, Ann. of math., 32, 378-390, (1931) · 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.