Edge-independent spanning trees in augmented cubes

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 (AQ_n) 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 AQ_n, where N is the number of nodes in AQ_n, we solve the EISTs problem for this class of graphs. Since AQ_n is (2n−1)-regular, the result is optimal with respect to the number of EISTs constructed.