Degree condition for completely independent spanning trees

作者：Hong, Xia; Liu, Qinghai^*

来源：Information Processing Letters, 2016, 116(10): 644-648.

DOI：10.1016/j.ipl.2016.05.004

• Completely independent spanning tree
• Combinatorial problems

Let T-1, T-2,...,T-k be spanning trees of a graph G. For any two vertices u, v of G, if the paths from u to v in these k trees are pairwise openly disjoint, then we say that T-1, T-2,...,T-k are completely independent. Araki showed that a graph G on n >= 7 vertices has two completely independent spanning trees if the minimum degree delta(G) >= n/2. In this paper, we give a generalization: a graph G on n >= 4k - 1 vertices has k completely independent spanning trees if the minimum degree delta(G) >= k-1/kn. In fact, we prove a stronger result.

• 出版日期2016-10
• 单位福州大学