Article ID Journal Published Year Pages File Type
4650022 Discrete Mathematics 2009 12 Pages PDF
Abstract

Given integers k,s,tk,s,t with 0≤s≤t0≤s≤t and k≥0k≥0, a (k,t,s)(k,t,s)-linear forest FF is a graph that is the vertex disjoint union of tt paths with a total of kk edges and with ss of the paths being single vertices. If the number of single vertex paths is not critical, the forest FF will simply be called a (k,t)(k,t)-linear forest. A graph GG of order n≥k+tn≥k+t is (k,t)(k,t)-hamiltonian if for any (k,t)(k,t)-linear forest FF there is a hamiltonian cycle containing FF. More generally, given integers mm and nn with k+t≤m≤nk+t≤m≤n, a graph GG of order nn is (k,t,s,m)(k,t,s,m)-pancyclic if for any (k,t,s)(k,t,s)-linear forest FF and for each integer rr with m≤r≤nm≤r≤n, there is a cycle of length rr containing the linear forest FF. Minimum degree conditions and minimum sum of degree conditions of nonadjacent vertices that imply that a graph is (k,t,s,m)(k,t,s,m)-pancyclic (or just (k,t,m)(k,t,m)-pancyclic) are proved.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,