ArticleOriginal scientific text

Title

Linear forests and ordered cycles

Authors 1, 2, 3, 3, 4,

Affiliations

  1. Georgia State University, Atlanta, GA 30303
  2. University of Memphis, Memphis, TN 38152
  3. Emory University, Atlanta, GA 30322
  4. Drew University, Madison, NJ 07940
  5. Emory University, Atlanta, GA 30322, Technische Universität Berlin, Berlin, Germany

Abstract

A collection L=P¹P²...Pt (1 ≤ t ≤ k) of t disjoint paths, s of them being singletons with |V(L)| = k is called a (k,t,s)-linear forest. A graph G is (k,t,s)-ordered if for every (k,t,s)-linear forest L in G there exists a cycle C in G that contains the paths of L in the designated order as subpaths. If the cycle is also a hamiltonian cycle, then G is said to be (k,t,s)-ordered hamiltonian. We give sharp sum of degree conditions for nonadjacent vertices that imply a graph is (k,t,s)-ordered hamiltonian.

Keywords

hamilton cycles, graph linkages

Bibliography

  1. B. Bollobás and A. Thomason, Highly Linked Graphs, Combinatorics, Probability, and Computing, (1993) 1-7.
  2. J.R. Faudree, R.J. Faudree, R.J. Gould, M.S. Jacobson and L. Lesniak, On k-Ordered Graphs, J. Graph Theory 35 (2000) 69-82, doi: 10.1002/1097-0118(200010)35:2<69::AID-JGT1>3.0.CO;2-I
  3. R.J. Faudree, R.J., Gould, A. Kostochka, L. Lesniak, I. Schiermeyer and A. Saito, Degree Conditions for k-ordered hamiltonian graphs, J. Graph Theory 42 (2003) 199-210, doi: 10.1002/jgt.10084.
  4. Z. Hu, F. Tian and B. Wei, Long cycles through a linear forest, J. Combin. Theory (B) 82 (2001) 67-80, doi: 10.1006/jctb.2000.2022.
  5. H. Kierstead, G. Sarkozy and S. Selkow, On k-Ordered Hamiltonian Graphs, J. Graph Theory 32 (1999) 17-25, doi: 10.1002/(SICI)1097-0118(199909)32:1<17::AID-JGT2>3.0.CO;2-G
  6. W. Mader, Existenz von n-fach zusammenhängenden Teilgraphen in Graphen genügend grosser Kantendichte, Abh. Math. Sem. Univ. Hamburg 37 (1972) 86-97, doi: 10.1007/BF02993903.
  7. L. Ng and M. Schultz, k-Ordered Hamiltonian Graphs, J. Graph Theory 24 (1997) 45-57, doi: 10.1002/(SICI)1097-0118(199701)24:1<45::AID-JGT6>3.0.CO;2-J
  8. R. Thomas and P. Wollan, An Improved Edge Bound for Graph Linkages, preprint.
Pages:
359-372
Main language of publication
English
Received
2002-08-02
Accepted
2004-07-19
Published
2004
Exact and natural sciences