Constructing spanning trees in augmented cubes

The spanning trees T-1, T-2, . . . , T-k of G are edge-disjoint spanning trees (EDSTs) if they are pairwise edge-disjoint. In addition to it if they are pairwise internally vertex disjoint then they are called completely independent spanning trees (CISTs) in G. In networks, EDSTs and CISTs are useful to increase fault tolerance, bandwidth, and security. The possible geometric configurations in which hundreds or even thousands of processors may be linked together are examined to find the geometry that best supports computations. A much-studied topology is the hypercube and its variants. The n-dimensional augmented cube, denoted as AQ(n), a variation of the hypercube possesses several embeddable properties that the hypercube and its other variations do not possess. Wang et al. (2017) asked to derive an algorithm that constructs edge-disjoint spanning trees in an augmented cube. In this paper, construction of n - 1 edge-disjoint spanning trees of the augmented cube AQ(n) (n >= 3) is given. The result is optimal with respect to the number of edge-disjoint spanning trees. Pai and Chang (2016) provided an approach for constructing two CISTs in several hypercube-variant networks with diameter 2n - 1. They asked to design algorithms to construct more than two CISTs in high dimensional hypercube-variant networks with a smaller diameter. For AQ(n) (n >= 6), we construct four completely independent spanning trees of which two trees are with diameters 2n - 5 and two trees are with diameters 2n - 3. (C) 2018 Elsevier Inc. All rights reserved.