Pancyclicity and bipancyclicity of conditional faulty folded hypercubes

A graph is said to be pancyclic if it contains cycles of every length from its girth to its order inclusive; and a bipartite graph is said to be bipancyclic if it contains cycles of every even length from its girth to its order. The pancyclicity or the bipancyclicity of a given network is an important factor in determining whether the network's topology can simulate rings of various lengths. An n-dimensional folded hypercube FQ(n) is an attractive variant of an n-dimensional hypercube Q(n) that is obtained by establishing some extra edges between the vertices of Q(n). FQ(n) for any odd n is known to be bipartite. In this paper, we explore the pancyclicity and bipancyclicity of FQ(n). For any FQ(n) (n >= 2) with at most 2n - 3 faulty edges, where each vertex is incident to at least two fault-free edges, we prove that there exists a fault-free cycle of every even length from 4 to 2(n); and when n >= 2 is even, we prove there also exists a fault-free cycle of every odd length from n + 1 to 2(n) - 1. The result is optimal with respect to the number of faulty edges tolerated. (C) 2010 Elsevier Inc. All rights reserved.