Constructing Independent Spanning Trees on Pancake Network

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 Examining 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

Date of Award	2019
Original language	English
Supervisor	Sun-Yuan Hsieh (Supervisor)