关于图的圈和退化圈分拆的一个注记(英文)  

A Note on Partition of a Graph into Cycles and Degenerated Cycles

作　　者：徐敏[1] 徐新萍[2] 

机构地区：[1]中国科学技术大学数学系,合肥230026 [2]江苏教育学院数学与计算机科学系,南京210013

出　　处：《中国科学技术大学学报》2003年第6期663-667,共5页JUSTC

基　　金：SupportedbyNNSFC (No .1 0 2 71 1 1 4andNo .1 0 30 1 0 31 )

摘　　要：设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.

关 键 词：圈 分拆 最大度 退化圈 

分 类 号：O157[理学—数学]