2017/10/05 by Tian, Yingzhi, Lai, Hong-Jian, Xu, Liqiong +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1710.01883
Mader [J. Graph Theory 65 (2010) 61-69] conjectured that for every positive integer k and every finite tree T with order m, every k-connected, finite graph G with δ(G)≥ \lfloor(3)/(2)k\rfloor+m-1 contains a subtree T' isomorphic to T such that G-V(T') is k-connected. The conjecture has been verified for paths, trees when k=1, and stars or double-stars when k=2. In this paper we verify the conjecture for two classes of trees when k=2. For digraphs, Mader [J. Graph Theory 69 (2012) 324-329] conjectured that every k-connected digraph D with minimum semi-degree δ(D)=min\δ+(D),δ-(D)\≥ 2k+m-1 for a positive integer m has a dipath P of order m with κ(D-V(P))≥ k. The conjecture has only been verified for the dipath with m=1, and the dipath with m=2 and k=1. In this paper, we prove that every strongly connected digraph with minimum semi-degree δ(D)=min\δ+(D),δ-(D)\≥ m+1 contains an oriented tree T isomorphic to some given oriented stars or double-stars with order m such that D-V(T) is still strongly connected.