Constructing Independent Spanning Trees on Pancake Networks

Dun Wei Cheng, Chih Te Chan, Sun Yuan Hsieh

Research output: Contribution to journalArticle


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.

Original languageEnglish
Article number8943420
Pages (from-to)3427-3433
Number of pages7
JournalIEEE Access
Publication statusPublished - 2020 Jan 1

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Materials Science(all)
  • Engineering(all)

Fingerprint Dive into the research topics of 'Constructing Independent Spanning Trees on Pancake Networks'. Together they form a unique fingerprint.

  • Cite this