| Summary: | Let T1, T2, . . . , Tk 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 T1, T2, . . . , Tk 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 δ(G) ≥ k and n ≥ 2k, then the k-th power Gk of G has k completely independent spanning trees.
|
|---|