COMPLETELY INDEPENDENT SPANNING TREES IN k-TH POWER OF GRAPHS

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 the square of a 2-connected graph G on n vertices with n >= 4 has two completely independent spanning trees. In this paper, we prove that the k-th power of a k-connected graph G on n vertices with n >= 2k has k completely independent spanning trees. In fact, we prove a stronger result: if G is a connected graph on n vertices with delta(G) >= k and n >= 2k, then the k-th power G(k) of G has k completely independent spanning trees.