Pancyclic graphs and linear forests |
| |
Authors: | Ralph J Faudree Michael S Jacobson |
| |
Institution: | a Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, United States b Department of Math and Computer Science, Emory University, Atlanta, GA 30322, United States c Department of Mathematics, University of Colorado at Denver, Denver, CO 80217, United States |
| |
Abstract: | 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. If the number of single vertex paths is not critical, the forest F will simply be called a (k,t)-linear forest. A graph G of order n≥k+t is (k,t)-hamiltonian if for any (k,t)-linear forest F there is a hamiltonian cycle containing F. More generally, 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. Minimum degree conditions and minimum sum of degree conditions of nonadjacent vertices that imply that a graph is (k,t,s,m)-pancyclic (or just (k,t,m)-pancyclic) are proved. |
| |
Keywords: | Pancyclic Linear forest Minimum degree |
本文献已被 ScienceDirect 等数据库收录! |
|