带限制条件的凯莱图顶点划分研究

项目名称： 带限制条件的凯莱图顶点划分研究

项目编号： No.11426085

项目类型： 专项基金项目

立项/批准年度： 2015

项目学科： 数理科学和化学

项目作者： 李锐

作者单位： 河海大学

项目金额： 3万元

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

中文关键词： 划分；连通度；最小度；无三圈图；

英文摘要： Graph partitioning problems ask for a partition of the vertex or edge set of a graph into subsets satisfying some further requirements. First, it concerns with the existence of the partition as desired. After that, it optimizes a cost function associated with the partitions. Cayley graph, due to its simple structure and high symmetry, has attracted more attention from graph researchers, and become an important research field of graph theory. Cayley graph is often designed as the topology structure of an interconnection network. So the structural characteristics of Cayley graph, and some parameters related to the stability of networks, like connectivity and super connectivity and restricted connectivity have been studied extensively. This project focuses on the partitions of Cayley graphs with condition on the connectivity and minimum degree. For any positive integer k, we want to find a linear function f(k) such that the vertex set of every f(k)-connected Cayley graph can be partitioned into non-empty sets S and T such that the two subgraphs induced by S and T are both k-connected and every vertex in S has at least k neighbours in T.

英文关键词： partition；connectivity；minimum degree；triangle-free；