首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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≤st 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 nk+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+tmn, 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 mrn, 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号