Dirac's Condition for Completely Independent Spanning Trees
Dirac's Condition for Completely Independent Spanning Trees
复制标题
DOI：
10.1002/jgt.21780
复制
发表时间：
2014-11
影响因子：
0.9
通讯作者：
Toru Araki
中科院分区：
文献类型：
--
作者：
Toru Araki
图G的两个生成树T1和T2是完全独立的，如果对于任意两个顶点u和v，T1和T2中从u到v的路是内部不相交的。本文给出了完全独立生成树存在的两个充分条件。首先，我们证明了一个n阶图有两个完全独立的生成树，如果图的最小度至少是n/2。然后，我们证明了2连通图的平方有两个完全独立的生成树。这些条件是已知的哈密尔顿图的充分条件。
Two spanning trees T1 and T2 of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T1 and T2 are internally disjoint. In this article, we show two sufficient conditions for the existence of completely independent spanning trees. First, we show that a graph of n vertices has two completely independent spanning trees if the minimum degree of the graph is at least n/2 . Then, we prove that the square of a 2‐connected graph has two completely independent spanning trees. These conditions are known to be sufficient conditions for Hamiltonian graphs.