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 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.
Keywords:
completely independent spanning tree, power of graphs, spanning trees

Links:
PDF