کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427030 | 686424 | 2016 | 5 صفحه PDF | دانلود رایگان |
• We study the existence of k completely independent spanning trees in a graph with large minimum degree.
• We generalize Araki's result on the existence of two completely independent spanning trees.
• We obtain a balanced CIST-partition instead of CIST-partition under the well-known Dirac's condition, which strengths Araki's result.
Let T1,T2,…,TkT1,T2,…,Tk be spanning trees of a graph G . For any two vertices u,vu,v of G, if the paths from u to v in these k trees are pairwise openly disjoint, then we say that T1,T2,…,TkT1,T2,…,Tk are completely independent. Araki showed that a graph G on n≥7n≥7 vertices has two completely independent spanning trees if the minimum degree δ(G)≥n/2δ(G)≥n/2. In this paper, we give a generalization: a graph G on n≥4k−1n≥4k−1 vertices has k completely independent spanning trees if the minimum degree δ(G)≥k−1kn. In fact, we prove a stronger result.
Journal: Information Processing Letters - Volume 116, Issue 10, October 2016, Pages 644–648