Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650136 | Discrete Mathematics | 2009 | 8 Pages |
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}.