Nonseparating trees in 2-connected graphs and oriented trees in strongly connected digraphs
Nonseparating trees in 2-connected graphs and oriented trees in strongly connected digraphs
复制标题
二连通图中的不分离树和强连通有向图中的有向树
DOI：
10.1016/j.disc.2018.10.001
复制
发表时间：
2019-02-01
影响因子：
0.8
通讯作者：
Meng, Jixiang
中科院分区：
文献类型：
--
作者：
Tian, Yingzhi;Lai, Hong-Jian;Meng, Jixiang
Mader (2010) conjectured that for every positive integer k and every finite tree T with order m, every k-connected, finite graph G with delta(G) >= [3/2 k] + 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 (2012) conjectured that every k-connected digraph D with minimum semi-degree delta(D) = min{delta(+)(D), delta(-)(D)} >= 2k m - 1 for a positive integer m has a dipath P of order m with k(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 delta(D) = min{delta(+)(D), delta(-)(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. (C) 2018 Elsevier B.V. All rights reserved.
