对称图中保持连通度的子图的研究

In 2010 and 2012, Mader proposed two conjectures: (1) For every positive integer k and every finite tree T, every k-connected graph G with δ(G)≥[3k/2]-1+|T| contains a subgraph W which is isomorphic to T such that G-V(W) is still k-connected; (2) Every k-connected digraph D with δ(D)≥2k+m for a non-negative integer m has a path P of length m such that D-V(P) is still k-connected. In this project, we will study these two conjectures on symmetric graphs. Because these two conjectures are closely related to the fault tolerance of networks and symmetric graphs are important in network design, this project aims at providing a theoretical basis for those issues concerning with fault tolerance of networks, and also aims at accumulating theoretical insight for the eventual settlement of the above two conjectures proposed by Mader.

Mader在2010年和2012年分别提出猜想：（1）对所有的正整数k和树T，每个最小度δ(G)≥[3k/2]-1+|T|的k连通图G都包含一个同构于T的子图W使得G-V(W)仍然是k连通的；（2）每个最小度δ(D)≥2k+m的k连通有向图D都存在阶为m的有向路P使得D-V(P)仍然是k连通的。本项目拟在对称图中研究这两个猜想。由于这两个猜想与网络容错度密切相关，又由于对称图在网络设计中占有重要的地位，本项目旨在为网络容错问题提供理论依据，并对Mader猜想的最终解决提供理论积累。

本项目主要研究对称网络的容错性质，探索Mader猜想的对称情形，即：（1）对所有的正整数k和树T，每个最小度δ(G)≥[3k/2]-1+|T|的k连通对称图（如Cayley图和点传递图）G都包含一个同构于T的子图W使得G-V(W)仍然是k连通的；（2）每个最小度δ(D)≥2k+m的k连通有向对称图（如Cayley有向图和点传递有向图）D都存在阶为m的有向路P使得D-V(P)仍然是k连通的。对于Mader猜想的对称情形，我们没有得到完全解答。但我们对图的容错性研究得到了下面结果：给出一个图序列是超边连通的充分必要条件；给出全图是超点连通、超限制边连通的充分条件。