# Linear forests and ordered cycles

Guantao Chen; Ralph J. Faudree; Ronald J. Gould; Michael S. Jacobson; Linda Lesniak; Florian Pfender

Discussiones Mathematicae Graph Theory (2004)

- Volume: 24, Issue: 3, page 359-372
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topGuantao Chen, et al. "Linear forests and ordered cycles." Discussiones Mathematicae Graph Theory 24.3 (2004): 359-372. <http://eudml.org/doc/270240>.

@article{GuantaoChen2004,

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

author = {Guantao Chen, Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson, Linda Lesniak, Florian Pfender},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {hamilton cycles; graph linkages; Hamilton cycles},

language = {eng},

number = {3},

pages = {359-372},

title = {Linear forests and ordered cycles},

url = {http://eudml.org/doc/270240},

volume = {24},

year = {2004},

}

TY - JOUR

AU - Guantao Chen

AU - Ralph J. Faudree

AU - Ronald J. Gould

AU - Michael S. Jacobson

AU - Linda Lesniak

AU - Florian Pfender

TI - Linear forests and ordered cycles

JO - Discussiones Mathematicae Graph Theory

PY - 2004

VL - 24

IS - 3

SP - 359

EP - 372

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

LA - eng

KW - hamilton cycles; graph linkages; Hamilton cycles

UR - http://eudml.org/doc/270240

ER -

## References

top- [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 Zbl0958.05083
- [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. Zbl1014.05045
- [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. Zbl1026.05065
- [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 Zbl0929.05055
- [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. Zbl0215.33803
- [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. Zbl1056.05091

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.