【摘要】 设G是一个顶点数为n的图,k为任意正整数且k≤n.HikoeEnomoto和李浩证明了:如果一对不相邻顶点的度和至少为n-k+1,其中k≤n,则除了k=2,G=C5,G能被剖分成k个子图Hi,1≤i≤k,其中Hi是圈或K1或K2.本文中证明了任何一对不相邻顶点的度和至少为n-k,则G能被剖分成k个子图Hi,1≤i≤k,其中Hi是圈或是路.更多还原

【Abstract】 Let G be a graph of order n and k be a positive integer with k≤n. Hikoe Enomoto and Hao Li proved that if the degree sum of any pair of nonadjacent vertices is at least n-k+1, then G can be partitioned into k subgraphs Hi, 1≤i≤k, where Hi is a cycle or K1 or K2, except G=C5 and k=2. We prove if the degree sum of any pair of nonadjacent vertices is at least n-k, then G can be partitioned into k subgraphs Hi, 1≤i≤k, where Hi is a cycle or a path.更多还原