On the Independent Spanning Trees Problem in a Hypercube

Abstract

A set of spanning trees rooted at some vertex r in G is said to be independent if for each vertex v in G, v¹r, the paths from v to r in any two trees are vertex-disjoint. If the connectivity of G is k, the independent spanning trees problem is to construct k independent spanning trees rooted at each vertex. This problem is still open for general graph with connectivity greater than four. However, it has been proved that a k-dimensional hypercube (or Qk) has k independent spanning trees rooted at an arbitrary vertex. In this paper, a simple algorithm is proposed to construct k optimal independent spanning trees on Qk . The algorithm is also suitable for parallel or distributed system.