在1-连通和2-连通的二部图中保持连通度的一些树的研究

On the Connectivity Keeping some Trees in Connected and 2-Connected Bipartite Graphs

在2010年,Mader猜想对任意的阶为m的树T,每一个最小度至少为■的k-连通图G中存在一个子树■,使得G-V (T′)仍然是k-连通的.对于二部图,提出了类似的猜想:对任意的二部划分为X和Y的树T (记t=max{|X|,|Y|}),每一个最小度至少为k+t的k-连通的二部图G中存在一个子树■,使得G-V (T′)仍然是k-连通的.最后验证了该猜想在k=1和k=2时,T是一个有至多3个内点的毛毛虫图的情形是对的.

In 2010,Mader conjectured that for any tree T of order m,every k-connected graph G with minimum degree at least■ contains a subtree ■ such that G-V (T′) is still k-connected.For bipartite graphs,we proposed a similar conjecture as follows:for every positive integer k and every finite tree T with bipartition X and Y (denote t=max{|X|,|Y|}),every k-connected bipartite graph G with minimum degree at least k+t contains a subtree ■ such that G-V (T′) is still k-connected.In this paper,we confirm this conjecture for all caterpillars whose internal vertices is at most 3 when k=1 and k=2.