Authors: X. Hong Title: Completely independent spanning trees in k-th power of graphs Source: Discussiones Mathematicae Graph Theory Received 28.04.2016, Revised 30.01.2017, Accepted 07.02.2017, doi: 10.7151/dmgt.2038 | |
Abstract: 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 δ(G)≥ k and n≥ 2k, then the k-th power G^{k} of G has k completely independent spanning trees. | |
Keywords: completely independent spanning tree, power of graphs, spanning trees | |
Links: |