|
Disjoint paths, planarizing cycles, and spanning walks
Author(s):
Xingxing
Yu
Journal:
Trans. Amer. Math. Soc.
349
(1997),
1333-1358.
MSC (1991):
Primary 05C38, 05C10, 57M15
MathSciNet review:
1401533
Retrieve article in:
PDF
This article is available free of charge
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:
- 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
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
|
