Geodesic-pancyclicity and fault-tolerant panconnectivity of augmented cubes

Abstract: Choudum and Sunitha [S.A. Choudum, V. Sunitha, Augmented cubes, Networks 40 (2002) 71–84] proposed the class of augmented cubes as a variation of hypercubes and showed that augmented cubes possess several embedding properties that the hypercubes and other variations do not possess. Recently, Hsu et al. [H.-C. Hsu, P.-L. Lai, C.-H. Tsai, Geodesic-pancyclicity and balanced pancyclicity of augmented cubes, Information Processing Letters 101 (2007) 227–232] showed that the n-dimensional augmented cube , n ⩾2, is weakly geodesic-pancyclic, i.e., for each pair of vertices and for each integer ℓ satisfying where d(u, v) denotes the distance between u and v in , there is a cycle of length ℓ that contains a u-v geodesic. In this paper, we obtain a stronger result by proving that , n ⩾2, is indeed geodesic-pancyclic, i.e., for each pair of vertices and for each integer ℓ satisfying , every u-v geodesic lies on a cycle of length ℓ. To achieve the result, we first show that , n ⩾3, remains panconnected (and thus is also edge-pancyclic) if is any faulty vertex. The result of fault-tolerant panconnectivity is the best possible in the sense that the number of faulty vertices in , n ⩾3, cannot be increased. [Copyright &y& Elsevier]