2025/11/10 by Hojin Chu, Shinya Fujita, Chu, Hojin +5
Computer Science · #Interconnection Networks and Systems #Advanced Graph Theory Research #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2511.06622
In 2012, Mader conjectured that for any tree T of order m, every k-connected graph G with minimum degree at least \lfloor (3k)/(2)\rfloor+m-1 contains a subtree T'≅ T such that G-V(T') remains k-connected. In 2022, Luo, Tian, and Wu considered an analogous problem for bipartite graphs and conjectured that for any tree T with bipartition (X,Y), every k-connected bipartite graph G with minimum degree at least k+max\|X|,|Y|\ contains a subtree T'≅ T such that G-V(T') remains k-connected. In this paper, we relax the bipartite assumption by considering triangle-free graphs and prove that for any tree T of order m, every k-connected triangle-free graph G with minimum degree at least 2k+3m-4 contains a subtree T' ≅ T such that G-V(T') remains k-connected. Furthermore, we establish refined results for specific subclasses such as bipartite graphs or graphs with girth at least five.