DMGT

Discussiones Mathematicae Graph Theory 24(3) (2004) 359-372
DOI: https://doi.org/10.7151/dmgt.1236

LINEAR FORESTS AND ORDERED CYCLES

Guantao Chen Georgia State University, Atlanta, GA 30303	Ralph J. Faudree University of Memphis, Memphis, TN 38152	Ronald J. Gould Emory University, Atlanta, GA 30322

Michael S. Jacobson Emory University, Atlanta, GA 30322	Linda Lesniak Drew University, Madison, NJ 07940	Florian Pfender Emory University, Atlanta, GA 30322 Technische Universität Berlin, Berlin, Germany

Abstract

A collection L = P¹∪P²∪... ∪P^t (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.

2000 Mathematics Subject Classification: 05C38, (05C35, 05C45).

References

[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.

Received 2 August 2002
Revised 19 July 2004