Fault-tolerant Edge-bipancyclicity Of The Hypercube

Let G be a graph. An even cycle of G is a cycle of even length. Let F be a faulty set of G. A vertex v in G is fault-free if v (?) F. An edge e=(u, v) in G is fault-free if u, v and e are not in F. A cycle in G is fault-free if it contains neither a faulty vertex nor a faulty edge. Let fv, fe be the number of faulty vertices and edges of F, respectively. G is edge-bipancyclic if each edge lies on a cycle of every even length from4to|V(G)|inclusive, where|V(G)|is the number of vertices of G. G is fault-tolerance edge-bipancyclic if G-F is edge-bipancyclic. In the thesis, we investigate the fault-tolerant edge-bipancyclicity of a bipartite n-dimensional hypercube Qn. We prove that each fault-free edge in Qn for n≥3lies on a fault-free cycle of every even length from6to2n-2fv inclusive if fv+fe≤2n-5, fe≤n-2and each fault-free vertex is incident with at least two fault-free edges. Tsai gave the following conjecture in [Information Processing Letters,102(2007)242-246]:Each fault-free edge of Qn for n≥4lies on a fault-free cycle of every even length from6to2n-2fv inclusive if fv+fe≤n-1and each fault-free vertex is incident with at least two fault-free edges. Combined with Xu et al’s work in [Information Processing Letters,96(2005)146-150], our result shows that this conjecture is affirmative.