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

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

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