摘要
设G是一个n阶图 ,k是满足 2 ≤k≤n的正整数 ,于是得到了如下结论 :如果图G的任何一对不相邻的顶点 {u ,v},都满足max{dG(u) ,dG(v) }≥(n -k+ 3) 2 ,则存在k个点不交的子图Hi,使得V(G) =V(H1)∪V(H2 )∪…∪V(Hk) ,其中Hi 为一个圈或一个点或一条边 .
Let G be a graph of order n and k be any positive integer with 2≤k≤n. In this paper, we prove that if the maximum degree of any pair of nonadjacent vertices is at least (n-k+3)2 (2≤k≤n), 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.
基金
SupportedbyNNSFC (No .1 0 2 71 1 1 4andNo .1 0 30 1 0 31 )
关键词
圈
分拆
最大度
退化圈
cycle
partition
maximum degree
degenerated cycle
