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 [Formula: see text] contains a subtree [Formula: see text] such that [Formula: see text] is k-connected. This conjecture has been proved for [Formula: see text]; however, it remains open for general [Formula: see text]; for [Formula: see text], partially affirmative answers have been shown, all of which restrict the class of trees to special subclasses such as trees of order at most 8, trees with diameter at most 4, trees with at most 5 internal vertices, and caterpillars. Instead of restricting the class of trees, we consider 2-connected graphs with girth conditions. We then show that Mader’s conjecture is true for every 2-connected graph G with [Formula: see text], where g(G) and [Formula: see text] denote the girth of G and the minimum degree of a vertex in G, respectively. Besides, we show that for every 2-connected graph G with [Formula: see text], the lower bound of [Formula: see text] on [Formula: see text] in Mader’s conjecture can be improved to [Formula: see text] if [Formula: see text]. Moreover, the lower bound of [Formula: see text] (respectively, [Formula: see text]) on g(G) in these results can be improved to [Formula: see text] (respectively, [Formula: see text] with [Formula: see text]) if no six (respectively, four) cycles of length g(G) have a common path of length [Formula: see text] in 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 [Formula: see text] time algorithms for finding a desired subtree in a given 2-connected graph G satisfying the assumptions.