Completely independent spanning trees in k-th power of graphs
Discussiones Mathematicae Graph Theory
Received 28.04.2016, Revised 30.01.2017, Accepted 07.02.2017, doi: 10.7151/dmgt.2038
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.
completely independent spanning tree, power of graphs, spanning trees