The Construction of Multiple Independent Spanning Trees on Burnt Pancake Networks

Abstract

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 $v\in V(G)\setminus \{r\}$ , the paths from $v$ 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 $BP_{n}$ 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(N\times n)$ time, where $N$ is the number of nodes of $BP_{n}$ and $n$ is the dimension of the network. Furthermore, we prove the correctness of our proposed algorithm in constructing independent spanning trees.

Keywords

• Independent spanning trees
• burnt pancake network
• interconnection networks
• fault-tolerant transmission
• secure message distribution