Edge-bipancyclicity of a hypercube with faulty vertices and edges

A bipartite graph G = (V, E) is said to be bipancyclic if it contains a cycle of every even length from 4 to vertical bar V vertical bar. Furthermore, a bipancyclic G is said to be edge-bipancyclic if every edge of G lies on a cycle of every even length. Let F-v (respectively, F-e) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional hypercube Q(n). In this paper, we show that every edge of Q(n) - F-v - F-e lies on a cycle of every even length from 4 to 2(n) - 2 vertical bar F-v vertical bar even if vertical bar F-v vertical bar + vertical bar F-e vertical bar <= n - 2, where n >= 3. Since Q(n) is bipartite of equal-size partite sets and is regular of vertex-degree n, both the number of faults tolerated and the length of a longest fault-free cycle obtained are worst-case optimal. (C) 2007 Elsevier B.V. All rights reserved.