Hamiltonian cycles through a linear forest
Takeshi Sugiyama · SUT Journal of Mathematics · 2004
Let G be a graph of order n. A graph is linear forest if every component is a path. Let S be a set of m edges of G that induces a linear forest. An edge xy ∈E(G) is called an S-edge if xy ∈S. An S-edge-length of a cycle in G is defined as the number of S-edges that it contains. We prove that if the degree sum in G of every pair of nonadjacent vertices of G is at least n + m, then G contains hamiltonian cycles of every S-edge-length between 0 and |S|.