Linear forests and ordered cycles
Guantao Chen ; Ralph J. Faudree ; Ronald J. Gould ; Michael S. Jacobson ; Linda Lesniak ; Florian Pfender
Discussiones Mathematicae Graph Theory, Tome 24 (2004), p. 359-372 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2004-01-01
EUDML-ID : urn:eudml:doc:270240 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1236,
     author = {Guantao Chen and Ralph J. Faudree and Ronald J. Gould and Michael S. Jacobson and Linda Lesniak and Florian Pfender},
     title = {Linear forests and ordered cycles},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {24},
     year = {2004},
     pages = {359-372},
     zbl = {1060.05054},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1236}
}

Guantao Chen; Ralph J. Faudree; Ronald J. Gould; Michael S. Jacobson; Linda Lesniak; Florian Pfender. Linear forests and ordered cycles. Discussiones Mathematicae Graph Theory, Tome 24 (2004) pp. 359-372. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1236/

[000] [1] B. Bollobás and A. Thomason, Highly Linked Graphs, Combinatorics, Probability, and Computing, (1993) 1-7.

[001] [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 | Zbl 0958.05083

[002] [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. | Zbl 1014.05045

[003] [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. | Zbl 1026.05065

[004] [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 | Zbl 0929.05055

[005] [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. | Zbl 0215.33803

[006] [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

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