Geodesic-pancyclicity and fault-tolerant panconnectivity of augmented cubes

摘要

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