Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions

摘要

Mader conjectured in 2010 that for any tree T of order m, every k-connected graph G with minimum degree at least left perpendicular3k/2right perpendicular + m - 1 contains a subtree T' congruent to T such that G - V(T') is k-connected. This conjecture has been proved for k = 1; however, it remains open for general k = 2; for k = 2, partially affirmative answers have been shown, all of which restrict the class of trees to special subclasses such as trees with at most 5 internal vertices, trees of order at most 8, trees with diameter at most 4, caterpillars, and spiders. We first extend the previously known subclass of trees for which Mader's conjecture for k = 2 holds; namely, we show that Mader's conjecture for k = 2 is true for the class of bifurcate quasi-unimodal caterpillars which includes every caterpillar and every tree of order m with diameter at least m - 4. Instead of restricting the class of trees, we next consider 2-connected graphs with girth conditions. We then show that Mader's conjecture is true for every 2-connected graph G with g(G) = delta(G) - 8, where g(G) and delta(G) denote the girth of G and theminimum degree of a vertex in G, respectively. Besides, we show that for every 2-connected graph G with g(G) = delta(G) - 7, the lower bound of m + 2 on delta(G) in Mader's conjecture can be improved to m+ 1 if m = 10. Moreover, the lower bound of delta(G) - 8 (respectively, delta(G) - 7) on g(G) in these results can be improved to delta(G)- 9 (respectively, delta(G) - 8 with m = 11) if no six (respectively, four) cycles of length g(G) have a common path of length inverted right perpendicularg(G)/2inverted left perpendicularg - 1 in G. We also show that Mader's conjecture holds for every 2-connected graph G with g degrees (G) = = delta(G) - 8, where g degrees (G) is the overlapping girth of G. Mader's conjecture is interesting not only from a theoretical point of view but also from a practical point of view, since it may be applied to fault-tolerant problems in communication networks. Our proofs lead to O(vertical bar V(G)vertical bar(4)) time algorithms for finding a desired subtree in a given 2-connected graph G satisfying the assumptions.