k-点连通图中保持连通度的子树的研究

In 2010 and 2012, Mader proposed two conjectures: (1) For every positive integer k and every finite tree T, every k-vertex-connected graph G with minimum degree δ(G)≥[3k/2]-1+|T| contains a subtree T' isomorphic to T such that G-V(T') is still k-vertex-connected; (2) Every k-vertex-connected digraph D with minimum degree δ(D)≥2k+m-1 for a positive integer m has a dipath P with m vertices such that D-V(P) is still k-vertex-connected. In this project, we mainly focus on these two conjectures. Specifically, we will study these two conjectures in the following three directions: for the small k; for some (directed) trees, such as (directed) stars and (directed) double-stars; for some classes of graphs (digraphs), such as addding girth condition to graphs (digraphs) and the bipartite graphs (digraphs). Based on these studies, we will also explore methods to solve the two Mader's conjectures for general graphs (digraphs).

Mader在2010年和2012年分别提出猜想：（1）对所有的正整数k和树T，每个最小度δ(G)≥[3k/2]-1+|T|的k-点连通图G都包含一个同构于T的子树T'使得G-V(T')仍然是k-点连通的；（2）每个满足最小度δ(D)≥2k+m-1的k-点连通有向图D都存在阶为m的有向路P使得D-V(P)仍然是k-点连通的。本项目的研究主要围绕着这两个猜想展开。具体地来说，我们会从下面三个方向来研究这两个猜想：对比较小的k；对一些特定的（定向）树，如（定向）星图和（定向）双星图；对一些特定图类，如加围长条件和二部（有向）图。在这些研究基础上，我们还将探索在一般（有向）图中解决Mader猜想的方法。

本项目主要围绕着Mader的k-点连通图中可去树猜想展开研究，即对所有的正整数k和树T，每个最小度δ(G)≥[3k/2]-1+|T|的k-点连通图G都包含一个同构于T的子图T`使得G-V(T`)仍然是k-点连通的。在本项目的支持下，我们按照研究计划，从以下三个方向展开研究：比较小的k；一些特定的树，如星图和双星图；一些特定图类，如加围长条件和二部图，得到了一系列与该猜想相关的研究成果。除此之外，我们也得到了图的连通性方面的研究成果。另外，本项目增加了对点（边）-k-极大r-一致超图的研究，得到了点（边）-k-极大r-一致超图边数上下界的研究成果。