Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Disjoint paths, planarizing cycles, and
spanning walks

Author: Xingxing Yu
Journal: Trans. Amer. Math. Soc. 349 (1997), 1333-1358
MSC (1991): Primary 05C38, 05C10, 57M15
MathSciNet review: 1401533
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study the existence of certain disjoint paths in planar graphs and generalize a theorem of Thomassen on planarizing cycles in surfaces. Results are used to prove that every 5-connected triangulation of a surface with sufficiently large representativity is hamiltonian, thus verifying a conjecture of Thomassen. We also obtain results about spanning walks in graphs embedded in a surface with large representativity.

References [Enhancements On Off] (What's this?)

  • 1. J. A. Bondy and U. S. R. Murty, Graph Theory with Applications. American Elsevier, 1976. MR 54:117
  • 2. R. Brunet, M. N. Ellingham, Z. Gao, A. Metzlar, and R. B. Richter, Spanning planar subgraphs of graphs in the torus and Klein bottle. J. Combin. Theory Ser. B 65 (1965) 7-22. MR 96g:05045
  • 3. R. A. Duke, On the genus and connectivity of hamiltonian graphs. Discrete Math., Vol. 2, No. 3 (1972) 199-206. MR 47:3221
  • 4. M. N. Ellingham and Z. Gao, Spanning trees in locally planar triangulations. J. Combinat. Theory Ser. B, 61 (1994) 178-198. MR 95m:05080
  • 5. Z. Gao and R. B. Richter, 2-Walks in circuit graphs. J. Combin. Theory Ser. B 62 (1994) 259-267. MR 96e:05093
  • 6. B. Grünbaum, Polytopes, graphs, and complexes. Bull. Amer. Math. Soc. 76 (1970) 1131-1201. MR 42:959
  • 7. J. C. Molluzzo, Problem. in ``Second International Conference on Combinatorial Mathematics'' (A. Gewirtz and L. V. Quintas, Eds.) pp. 556-567, The New York Academy of Sciences, New York, 1979. MR 80j:05003
  • 8. C. St. J. A. Nash-Williams, Unexplored and semi-explored territories in graph theory. New Directions in Graph Theory, Academic Press, New York (1973) 169-176. MR 52:7944
  • 9. M. D. Plummer, Problem in infinite and finite sets. Coll. Math. Soc. J. Bolyai 10, Vol. III (A. Hajnal, R. Rado and V. T. Sós, Eds.), North-Holland, Amsterdam (1975) 1549-1550. MR 50:12526
  • 10. R. Thomas and X. Yu, 4-Connected projective-planar graphs are hamiltonian. J. Combinat. Theory Ser. B 62 (1994) 114-132. MR 95j:05133
  • 11. R. Thomas and X. Yu, 5-connected toroidal graphs are hamiltonian. J. Combinat. Theory Ser. B., in press.
  • 12. C. Thomassen, A theorem on paths in planar graphs. J. Graph Theory 7 (1983) 169-176. MR 84i:05075
  • 13. C. Thomassen, Embeddings of graphs with no short noncontractible cycles. J. Combinat. Theory Ser B 48 (1990) 155-177. MR 91b:05069
  • 14. C. Thomassen, Trees in triangulations. J. Combinat. Theory Ser. B 60 (1994) 56-62. MR 95e:05039
  • 15. C. Thomassen, 5-Coloring maps on surfaces. J. Combinat. Theory Ser. B 59 (1993) 89-105. MR 94h:05031
  • 16. W. T. Tutte, A theorem on planar graphs. Trans. Amer. Math. Soc. 82 (1956) 99-116. MR 18:408e
  • 17. H. Whitney, A theorem on graphs. Ann. of Math. 32 (1931) 378-390.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 05C38, 05C10, 57M15

Retrieve articles in all journals with MSC (1991): 05C38, 05C10, 57M15

Additional Information

Xingxing Yu
Affiliation: School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332
Address at time of publication: Department of Mathematics, Vanderbilt University, Nashville, Tennessee 37240

Keywords: bridge, disjoint paths, embedding, Hamilton cycle, representativity, walk
Received by editor(s): August 20, 1993
Additional Notes: Partially supported by NSF grants DMS–9105173 and DMS–9301909
Article copyright: © Copyright 1997 American Mathematical Society

American Mathematical Society