| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427030 | Information Processing Letters | 2016 | 5 Pages |
•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.
