کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650136 1342477 2009 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Weak cycle partition involving degree sum conditions
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Weak cycle partition involving degree sum conditions
چکیده انگلیسی

Let GG be a graph of order nn and kk a positive integer. A set of subgraphs H={H1,H2,…,Hk}H={H1,H2,…,Hk} is called a kk-degenerated cycle partition   (abbreviated to kk-DCP) of GG if H1,…,HkH1,…,Hk are vertex disjoint subgraphs of GG such that V(G)=⋃i=1kV(Hi) and for all ii, 1≤i≤k1≤i≤k, HiHi is a cycle or K1K1 or K2K2. If, in addition, for all ii, 1≤i≤k1≤i≤k, HiHi is a cycle or K1K1, then HH is called a kk-weak cycle partition   (abbreviated to kk-WCP) of GG. It has been shown by Enomoto and Li that if |G|=n≥k|G|=n≥k and if the degree sum of any pair of nonadjacent vertices is at least n−k+1n−k+1, then GG has a kk-DCP, except G≅C5G≅C5 and k=2k=2. We prove that if GG is a graph of order n≥k+12n≥k+12 that has a kk-DCP and if the degree sum of any pair of nonadjacent vertices is at least 3n+6k−54, then either GG has a kk-WCP or k=2k=2 and GG is a subgraph of K2∪Kn−2∪{e}K2∪Kn−2∪{e}, where ee is an edge connecting V(K2)V(K2) and V(Kn−2)V(Kn−2). By using this, we improve Enomoto and Li’s result for n≥max{k+12,10k−9}n≥max{k+12,10k−9}.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 4, 6 March 2009, Pages 647–654
نویسندگان
, ,