Constructing Independent Spanning Trees on Pancake Networks

Abstract

For any graph G, the set of independent spanning trees (ISTs) is defined as the set of spanning trees in G. All ISTs have the same root, paths from the root to another vertex between distinct trees are vertex-disjoint and edge-disjoint. The construction of multiple independent trees on a graph has numerous applications, such as fault-tolerant broadcasting and secure message distribution. The pancake graph is a subclass of Cayley graphs and since Cayley graphs are crucial for designing interconnection networks, constructing ISTs on these graphs is necessary for many practical applications. In this paper, we propose algorithms for constructing ISTs on pancake graph. Examine the use of our algorithm for constructing ISTs on pancake graph in different dimensions. We also present proofs about the construction of ISTs on pancake graph to verify that the correctness of these algorithms.

Keywords

• Interconnection networks
• independent spanning trees
• pancake networks