## Disjoint paths, planarizing cycles, and spanning walks

HTML articles powered by AMS MathViewer

- by Xingxing Yu PDF
- Trans. Amer. Math. Soc.
**349**(1997), 1333-1358 Request permission

## 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

- J. A. Bondy and U. S. R. Murty,
*Graph theory with applications*, American Elsevier Publishing Co., Inc., New York, 1976. MR**0411988**, DOI 10.1007/978-1-349-03521-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**, DOI 10.1006/jctb.1995.1041 - Richard A. Duke,
*On the genus and connectivity of Hamiltonian graphs*, Discrete Math.**2**(1972), no. 3, 199–206. MR**314670**, DOI 10.1016/0012-365X(72)90003-9 - 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**, DOI 10.1006/jctb.1994.1043 - Zhicheng Gao and R. Bruce Richter,
*$2$-walks in circuit graphs*, J. Combin. Theory Ser. B**62**(1994), no. 2, 259–267. MR**1305052**, DOI 10.1006/jctb.1994.1068 - Branko Grünbaum,
*Polytopes, graphs, and complexes*, Bull. Amer. Math. Soc.**76**(1970), 1131–1201. MR**266050**, DOI 10.1090/S0002-9904-1970-12601-5 - 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**, DOI 10.1070/rm1979v034n06abeh003276 - 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** - A. Hajnal, R. Rado, and Vera T. Sós (eds.),
*Infinite and finite sets. Vols. I, II, III*, Colloquia Mathematica Societatis János Bolyai, Vol. 10, North-Holland Publishing Co., Amsterdam-London; János Bolyai Mathematical Society, Budapest, 1975. Dedicated to Paul Erdős on his 60th birthday. MR**0360076** - 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**, DOI 10.1006/jctb.1994.1058 - R. Thomas and X. Yu, 5-connected toroidal graphs are hamiltonian.
*J. Combinat. Theory Ser. B*., in press. - Carsten Thomassen,
*A theorem on paths in planar graphs*, J. Graph Theory**7**(1983), no. 2, 169–176. MR**698698**, DOI 10.1002/jgt.3190070205 - Carsten Thomassen,
*Embeddings of graphs with no short noncontractible cycles*, J. Combin. Theory Ser. B**48**(1990), no. 2, 155–177. MR**1046752**, DOI 10.1016/0095-8956(90)90115-G - Carsten Thomassen,
*Trees in triangulations*, J. Combin. Theory Ser. B**60**(1994), no. 1, 56–62. MR**1256583**, DOI 10.1006/jctb.1994.1005 - Carsten Thomassen,
*Five-coloring maps on surfaces*, J. Combin. Theory Ser. B**59**(1993), no. 1, 89–105. MR**1234386**, DOI 10.1006/jctb.1993.1057 - Cahit Arf,
*Untersuchungen über reinverzweigte Erweiterungen diskret bewerteter perfekter Körper*, J. Reine Angew. Math.**181**(1939), 1–44 (German). MR**18**, DOI 10.1515/crll.1940.181.1 - H. Whitney, A theorem on graphs.
*Ann. of Math.*32 (1931) 378–390.

## 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
- Received by editor(s): August 20, 1993
- Additional Notes: Partially supported by NSF grants DMS–9105173 and DMS–9301909
- © Copyright 1997 American Mathematical Society
- 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