Linear forests and ordered cycles
Guantao Chen, Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson, Linda M. Lesniak, Florian Pfender · Discussiones Mathematicae Graph Theory · 2004
A collection L = P 1 ∪ P 2 ∪ · · · ∪ 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.