Edge-independent spanning trees in augmented cubes

Yan Wang, Hong Shen, Jianxi Fan

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)


Edge-independent spanning trees (EISTs) have important applications in networks such as reliable communication protocols, one-to-all broadcasting, and secure message distribution, thus their designs in several classes of networks have been widely investigated. The n-dimensional augmented cube (AQn) is an important variant of the n-dimensional hypercube. It is (2n−1)-regular, (2n−1)-connected (n≠3), vertex-symmetric and has diameter of ⌈n/2⌉. In this paper, by proposing an O(Nlog⁡N) algorithm that constructs 2n−1 EISTs in AQn, where N is the number of nodes in AQn, we solve the EISTs problem for this class of graphs. Since AQn is (2n−1)-regular, the result is optimal with respect to the number of EISTs constructed.

Original languageEnglish
Pages (from-to)23-32
Number of pages10
JournalTheoretical Computer Science
Publication statusPublished - 29 Mar 2017
Externally publishedYes


  • Algorithm
  • Augmented cubes
  • Edge independent spanning trees
  • Fault-tolerance


Dive into the research topics of 'Edge-independent spanning trees in augmented cubes'. Together they form a unique fingerprint.

Cite this