Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions
Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions
复制标题
DOI：
10.1007/s00453-021-00833-8
复制
发表时间：
2020-04
期刊：
影响因子：
--
通讯作者：
Toru Hasunuma
中科院分区：
文献类型：
--
作者：
Toru Hasunuma
Mader在2010年猜想，对于任意有序的树T，每个具有最小度的k连通图G至少包含一个k连通的子树。这个猜想已被证明；然而，它仍然对一般人开放；因为，已经给出了部分肯定的答案，所有这些都将树的类别限制为特殊的子类，例如最多有 5 个内部顶点的树、最多 8 阶的树、直径最多为 4 的树、毛毛虫和蜘蛛。我们首先扩展了马德猜想所支持的先前已知的树子类；也就是说，我们证明了马德的猜想对于分叉准单峰毛毛虫类是正确的，该毛毛虫类至少包括每条毛毛虫和每棵具有直径的有序树。接下来我们不限制树的类别，而是考虑具有周长条件的 2 连通图。然后我们证明 Mader 的猜想对于每个 2-连通图 G 都成立，其中 g(G) 和 分别表示 G 的周长和 G 中顶点的最小度数。此外，我们证明对于每个2连通图Gwith，Mader猜想的下界可以改进为toif。此外，如果没有六个（分别为四个）lengthg(G) 循环具有长度为 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} 的公共路径，则这些结果中（分别）ong(G) 的下界可以改进为（分别，with） \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{文档}$$\left\lceil \frac{g(G)}{2} \right\rceil -1$$\end{文档} inG。我们还表明，Mader 的猜想对于每个 2-连通图 Gwith 都成立，其中 是 G 的重叠周长。马德的猜想不仅从理论角度来看很有趣，从实践角度来看也很有趣，因为它可以应用于通信网络中的容错问题。我们的证明导致了在给定的 2-连通图中找到满足假设的所需子树的时间算法。
Mader conjectured in 2010 that for any treeTof orderm, everyk-connected graphGwith minimum degree at leastcontains a subtreesuch thatisk-connected. This conjecture has been proved for; however, it remains open for general; for, 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 forholds; namely, we show that Mader’s conjecture foris true for the class of bifurcate quasi-unimodal caterpillars which includes every caterpillar and every tree of ordermwith diameter at least. 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 graphGwith, whereg(G) anddenote the girth ofGand the minimum degree of a vertex inG, respectively. Besides, we show that for every 2-connected graphGwith, the lower bound ofonin Mader’s conjecture can be improved toif. Moreover, the lower bound of(respectively,) ong(G) in these results can be improved to(respectively,with) if no six (respectively, four) cycles of lengthg(G) have a common path of length \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left\lceil \frac{g(G)}{2} \right\rceil -1$$\end{document} inG. We also show that Mader’s conjecture holds for every 2-connected graphGwith, whereis the overlapping girth ofG. 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 totime algorithms for finding a desired subtree in a given 2-connected graphGsatisfying the assumptions.