Cycle embedding in faulty wrapped butterfly graphs

Abstract

In this paper, we study the maximal length of cycle embedding in a faulty wrapped butterfly graph BFn with at most two faults in vertices and/or edges. When there is one vertex fault and one edge fault, we prove that the maximum cycle length is n2(n) - 2 if n is even and n2(n) - 1 if n is odd. When there are two faulty vertices, the maximum cycle length is n2(n) - 2 for odd n. All these results are optimal because the wrapped butterfly graph is bipartite if and only if n is even. (C) 2003 Wiley Periodicals, Inc.