中文摘要：

将图的顶点集或边集按特定要求划分成点子集或边子集的问题称为图的划分问题. 图的划分问题首先关注划分的存在性;其次,在这些划分上优化某些成本函数.凯莱图,由于构造简单以及高对称性,越来越受到图论学者的重视,已成为图论研究的一个重要领域. 凯莱图的结构特性,与网络稳定性相关的连通度,超连通性以及各类限制性连通度都得到了广泛研究. 本项目主要研究凯莱图的带连通度和最小度限制的划分问题.设k是任意正整数.我们希望找到一个线性函数f(k),使得任意f(k)-连通(或最小度为f(k))的凯莱图都存在划分 (S,T) 使得S和T所诱导的子图都是k-连通的(或最小度至少为k),且S中每个元素在T中都有k个邻点.