Panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes
As an enhancement on the hypercube Q(n), the augmented cube AQ(n), proposed by Choudura and Sunitha [S.A. Choudum, V. Sunitha, Augmented cubes, Networks, 40(2) (2002), 71-84], not only retains some of the favorable properties of Q(n) but also possesses some embedding properties that Q(n) does not. For example, AQ(n) contains cycles of all lengths from 3 to 2(n), but Q(n) contains only even cycles. In this paper, we obtain two stronger results by proving that AQ(n) contains paths, between any two distinct vertices, of all lengths from their distance to 2(n) - 1; and AQ(n) still contains cycles of all lengths from 3 to 2(n) when any (2n - 3) edges are removed from AQ(n). The latter is optimal since AQ(n) is (2n - 1)-regular. (c) 2006 Elsevier B.V. All rights reserved.
panconnected pancyclic augmented cube interconnection network fault-tolerant