On completely independent spanning trees in powers of graphs

Abstract

Let T₁,T₂,...,T_k be spanning trees of a graph G. For every two vertices u, v of G, if the paths from u to v in these A: trees are pairwise openly disjoint, then we say that T₁,T₂,..., T_k. are completely independent. Araki showed that the square of a 2-connected graph G on n(≥ 4) vertices has two completely independent spanning trees. In this paper, we determine two sufficient conditions which ensure that there exist k completely independent spanning trees in k-th power of graphs, and we also prove that the cube of a 2-connected graph G on n(≥ 6) vertices has 3 completely independent spanning trees, which improves Araki's result. © 2018 Utilitas Mathematica Publishing Inc. All rights reserved.