The Construction of Multiple Independent Spanning Trees on Burnt Pancake Networks

A set of the spanning trees in a graph G is called independent spanning trees if they have a common root r and for each vertex nu is an element of V (G) \ {r}, the paths from nu to r in any two trees are directed edge-disjoint and internally vertex-disjoint. The construction of independent spanning trees has many practical applications in reliable communication networks, such as fault-tolerant transmission and secure message distribution. A burnt pancake network BPn is a kind of Cayley graph, which has been proposed as the topology of an interconnection network. In this paper, we provide a two stages construction scheme that can be used to construct a maximal number of independent spanning trees on a burnt pancake network in O(Nxn) time, where N is the number of nodes of BPn and n is the dimension of the network. Furthermore, we prove the correctness of our proposed algorithm in constructing independent spanning trees.

Automated summary

The concept of independent spanning trees has significant implications in graph theory, studying the applications of multiple spanning trees in networks, such as fault-tolerant transmission and secure message distribution in communication networks. This paper proposes a scheme for constructing independent spanning trees on a burnt pancake network and proves the correctness of the algorithm.