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

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.

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

将图的顶点集或边集按特定要求划分成点子集或边子集的问题称为图的划分问题. 图的划分问题首先关注的是满足条件的划分的存在性. 图的划分问题已在算法和结构方面得到很广泛的研究. 图的划分问题有很多, 例如, 经典的顶点染色问题就是将图的顶点划分成独立点集的图的划分问题. 二部子图问题是我们所关注的另一类图的划分问题. 设~$S,T$ 是图~$G$的一个划分. 我们用记号~$(S, T)_G$ 表示由图~$G$ 中~$S,T$ 之间的边构成的二部子图. 众所周知, ~$(S, T)_G$ 的最小度能超过图~$G$ 最小度的一半. 于是一个有趣的问题是图~$G[S], G[T]$ 和~$(S,T)_G$ 的最小度或连通度能否同时达到一个比较大的值. 2003年, K\"{u}hn 和~Osthus 给出了一个否定的结论. 那么, 如果我们在上述问题中只要求 ~$(S,T)_G$ 的一部的最小度或连通度达到一个比较大的值会怎么样呢? ~K\"{u}hn 和 ~Osthus 的回答是肯定的. 对任意正整数 ~$\ell$, 他们证明了存在整数~$k_1(\ell)\leq 2^{11} \cdot3\ell^{2}$ 和~$k_2(\ell)\leq 2^{16}\ell^2$, 当~$\delta(G)\geqk_1(\ell)$ 时, 存在划分将~$V(G)$ 分成~$S$ 和~$T$ 使得~$\delta(G[S])\geq \ell\leq \delta(G[T])$ 且~$S$ 中的每个点在~$T$ 都至少有~$\ell$ 个邻点;当图的连通度大于~$k_2(\ell)$ 时, $V(G)$ 可以划分成~$S'$ 和~$T'$, 使得~$G[S']$ 和~$G[T']$ 都是~$\ell$-连通的且~$S'$ 中每个点在~$T'$ 中都至少有~$\ell$ 个邻点. 本课题中 , 我们首先在一般图上改进了~K\"{u}hn 和~Osthus 的结果, 将~$k_1(\ell)$ 的上界改进到~$2^4\cdot 17 \ell^2$. 接着我们考虑了无三圈图. 通过证明平均度至少是~$\frac 83 \ell$ 的无三圈图有~$\ell$-连通的子图, 我们在无三圈图中将~$k_2(\ell)$的上界改进到 $2^{16}\cdot 3^{-3}\ell^2$