Transactions of the American Mathematical Society

Author(s): Xingxing Yu
Journal: Trans. Amer. Math. Soc. 349 (1997), 1333-1358.
MSC (1991): Primary 05C38, 05C10, 57M15
Retrieve article in: PDF
This article is available free of charge

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.

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.

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

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
Email: yu@math.vanderbilt.edu

DOI: 10.1090/S0002-9947-97-01830-8
PII: S 0002-9947(97)01830-8
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
Copyright of article: Copyright 1997, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS