Department of Mathematics,University of Science and Technology of China, Hefei 230026, China;
Abstract:
The augmented cube AQn is a variation of the hypercube Qn. This paper considers the panconnectivity of AQn (n ⩾ 3) with at most 2n−5 faulty vertices and/or edges and shows that, for any two fault-free vertices u and v with distance d in AQn, there exist fault-free uv-paths of every length from d + 2 to 2n − f − 1, where f is the number of faulty vertices in AQn. The proof is based on an inductive construction.