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 AQ n , n  ⩾ 2, is weakly geodesic-pancyclic, i.e., for each pair of vertices u , v ∈ AQ n and for each integer l satisfying max { 2 d ( u , v ) , 3 } ⩽ l ⩽ 2 n where d ( u ,  v ) denotes the distance between u and v in AQ n , there is a cycle of length l that contains a u - v geodesic. In this paper, we obtain a stronger result by proving that AQ n , n  ⩾ 2, is indeed geodesic-pancyclic, i.e., for each pair of vertices u , v ∈ AQ n and for each integer l satisfying max { 2 d ( u , v ) , 3 } ⩽ l ⩽ 2 n , every u - v geodesic lies on a cycle of length l. To achieve the result, we first show that AQ n - f , n  ⩾ 3, remains panconnected (and thus is also edge-pancyclic) if f ∈ AQ n is any faulty vertex. The result of fault-tolerant panconnectivity is the best possible in the sense that the number of faulty vertices in AQ n , n  ⩾ 3, cannot be increased.