Geodesic
Linear forests and ordered cycles
Discussiones Mathematicae. Graph Theory, Tome 24 (2004) no. 3, pp. 359-372.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2004_24_3_a0,
     author = {Chen, Guantao and Faudree, Ralph and Gould, Ronald and Jacobson, Michael and Lesniak, Linda and Pfender, Florian},
     title = {Linear forests and ordered cycles},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {359--372},
     publisher = {mathdoc},
     volume = {24},
     number = {3},
     year = {2004},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2004_24_3_a0/}
}
TY  - JOUR
AU  - Chen, Guantao
AU  - Faudree, Ralph
AU  - Gould, Ronald
AU  - Jacobson, Michael
AU  - Lesniak, Linda
AU  - Pfender, Florian
TI  - Linear forests and ordered cycles
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2004
SP  - 359
EP  - 372
VL  - 24
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2004_24_3_a0/
LA  - en
ID  - DMGT_2004_24_3_a0
ER  - 
%0 Journal Article
%A Chen, Guantao
%A Faudree, Ralph
%A Gould, Ronald
%A Jacobson, Michael
%A Lesniak, Linda
%A Pfender, Florian
%T Linear forests and ordered cycles
%J Discussiones Mathematicae. Graph Theory
%D 2004
%P 359-372
%V 24
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2004_24_3_a0/
%G en
%F DMGT_2004_24_3_a0
Chen, Guantao; Faudree, Ralph; Gould, Ronald; Jacobson, Michael; Lesniak, Linda; Pfender, Florian. Linear forests and ordered cycles. Discussiones Mathematicae. Graph Theory, Tome 24 (2004) no. 3, pp. 359-372. http://geodesic.mathdoc.fr/item/DMGT_2004_24_3_a0/

[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:269::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:117::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:145::AID-JGT6>3.0.CO;2-J

[8] R. Thomas and P. Wollan, An Improved Edge Bound for Graph Linkages, preprint.