Constructing Node-Independent Spanning Trees in Augmented Cubes

Abstract

For a network, edge/node-independent spanning trees (ISTs) can not only tolerate faulty edges/nodes, but also be used to distribute secure messages. As important node-symmetric variants of the hypercubes, the augmented cubes have received much attention from researchers. The n-dimensional augmented cube AQ_n is both (2n ‒ 1)-edge-connected and (2n ‒ 1)-nodeconnected (n ≢ 3), thus the well-known edge conjecture and node conjecture of ISTs are both interesting questions in AQ_n. So far, the edge conjecture on augmented cubes was proved to be true. However, the node conjecture on AQ_n is still open. In this paper, we further study the construction principle of the node-ISTs by using the double neighbors of every node in the higher dimension. We prove the existence of 2k − 1 node-ISTs rooted at node 0 in $A{Q}_n(\underset{n-k}{\underbrace{\mathrm{00...0}}})(n\ge k\ge 4)$ by proposing an ingenious way of construction and propose a corresponding O(NlogN) time algorithm, where N = 2 ^k is the number of nodes in $A{Q}_n(\underset{n-k}{\underbrace{\mathrm{00...0}}})$ .