کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650022 1342472 2009 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Pancyclic graphs and linear forests
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Pancyclic graphs and linear forests
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 5, 28 March 2009, Pages 1178–1189
نویسندگان
, , ,