Linear Forests, k-Ordered, and Pancyclic Graphs
by
Ralph J. Faudree
University of Memphis

Given integers k, s, t with 0 ≤ s ≤ t and k ≥ 0, a (k, t, s)-linear forest F is a graph that is the vertex disjoint union of t paths with a total of k edges and with s of the paths being single vertices. Given integers m and n with k + t ≤ m ≤ n, a graph G of order n is (k, t, s, m)-pancyclic if for any (k, t, s)-linear forest F and for each integer r with m ≤ r ≤ n, there is a cycle of length r containing the linear forest F. If the paths of the forest F are required to appear on the cycle in a specified order, then the graph is said to be (k, t, s, m)-pancyclic ordered. If, in addition, each path in the system is oriented and must be traversed in the order of the orientation, then the graph is said to be strongly (k, t, s, m)-pancyclic ordered. Minimum degree conditions and minimum sum of degree conditions of nonadjacent vertices that imply a graph is (k, t, s, m)-pancyclic, as well as degree conditions that imply a graph is (strongly) (k, t, s, m)-pancyclic ordered will be given. Examples showing the sharpness of the conditions will be described. Problems and open questions related to these conditions will be presented.

Date received: May 7, 2009