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
DOI:
https://doi.org/10.1090/S0002-9947-97-01830-8
MathSciNet review:
1401533
Full-text PDF Free Access
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.
- 1. J. A. Bondy and U. S. R. Murty, Graph theory with applications, American Elsevier Publishing Co., Inc., New York, 1976. MR 0411988
- 2. Richard Brunet, Mark N. Ellingham, Zhicheng Gao, Alice Metzlar, and R. Bruce Richter, Spanning planar subgraphs of graphs in the torus and Klein bottle, J. Combin. Theory Ser. B 65 (1995), no. 1, 7–22. MR 1347338, https://doi.org/10.1006/jctb.1995.1041
- 3. Richard A. Duke, On the genus and connectivity of Hamiltonian graphs, Discrete Math. 2 (1972), no. 3, 199–206. MR 314670, https://doi.org/10.1016/0012-365X(72)90003-9
- 4. M. N. Ellingham and Zhicheng Gao, Spanning trees in locally planar triangulations, J. Combin. Theory Ser. B 61 (1994), no. 2, 178–198. MR 1280606, https://doi.org/10.1006/jctb.1994.1043
- 5. Zhicheng Gao and R. Bruce Richter, 2-walks in circuit graphs, J. Combin. Theory Ser. B 62 (1994), no. 2, 259–267. MR 1305052, https://doi.org/10.1006/jctb.1994.1068
- 6. Branko Grünbaum, Polytopes, graphs, and complexes, Bull. Amer. Math. Soc. 76 (1970), 1131–1201. MR 266050, https://doi.org/10.1090/S0002-9904-1970-12601-5
- 7. Allan Gewirtz and Louis V. Quintas (eds.), Second International Conference on Combinatorial Mathematics, Annals of the New York Academy of Sciences, vol. 319, New York Academy of Sciences, New York, 1979. Held in New York, April 4–7, 1978. MR 555999
- 8. C. St. J. A. Nash-Williams, Unexplored and semi-explored territories in graph theory, New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971) Academic Press, New York, 1973, pp. 149–186. MR 0387097
- 9. A. Hajnal, R. Rado, and Vera T. Sós (eds.), Infinite and finite sets. Vols. I, II, III, North-Holland Publishing Co., Amsterdam-London; János Bolyai Mathematical Society, Budapest, 1975. Dedicated to Paul Erdős on his 60th birthday; Colloquia Mathematica Societatis János Bolyai, Vol. 10. MR 0360076
- 10. Robin Thomas and Xingxing Yu, 4-connected projective-planar graphs are Hamiltonian, J. Combin. Theory Ser. B 62 (1994), no. 1, 114–132. MR 1290634, https://doi.org/10.1006/jctb.1994.1058
- 11. R. Thomas and X. Yu, 5-connected toroidal graphs are hamiltonian. J. Combinat. Theory Ser. B., in press.
- 12. Carsten Thomassen, A theorem on paths in planar graphs, J. Graph Theory 7 (1983), no. 2, 169–176. MR 698698, https://doi.org/10.1002/jgt.3190070205
- 13. Carsten Thomassen, Embeddings of graphs with no short noncontractible cycles, J. Combin. Theory Ser. B 48 (1990), no. 2, 155–177. MR 1046752, https://doi.org/10.1016/0095-8956(90)90115-G
- 14. Carsten Thomassen, Trees in triangulations, J. Combin. Theory Ser. B 60 (1994), no. 1, 56–62. MR 1256583, https://doi.org/10.1006/jctb.1994.1005
- 15. Carsten Thomassen, Five-coloring maps on surfaces, J. Combin. Theory Ser. B 59 (1993), no. 1, 89–105. MR 1234386, https://doi.org/10.1006/jctb.1993.1057
- 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
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:
https://doi.org/10.1090/S0002-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
Article copyright:
© Copyright 1997
American Mathematical Society