Cycles passing through a prescribed path in a hypercube with faulty edges
Let Q(n), denote an n-dimensional hypercube with n >= 2, P be a path of length h in Q(n), and F subset of E(Q(n))\E(P). Recently, Tsai proved that if 1 <= h <= n - 1 and vertical bar F vertical bar <= n - 1 - h, then in the graph Q(n)-F the path P lies on a cycle of every even length from 2h + 2 to 2(n), and P also lies on a cycle of length 2h if vertical bar F vertical bar <= h - 2. In this paper, we show that if 1 <= h <= 2n - 3 and broken vertical bar F vertical bar <= n - 2 - left perpendicularh/2right perpendicular, then in Q(n) - F the path P lies on a cycle of every even length from 2h + 2 to 2(n), and P also lies on a cycle of length 2h if P contains two edges of the same dimension or P is a shortest path and vertical bar F boolean AND E(Q(h))vertical bar <= h - 2, where Q(h) is the h-dimensional subcube containing the path P. Moreover, the upper bound 2n - 3 of h is sharp and the upper bound n - 2 - left perpendicularh/2rightperpendicular of vertical bar F vertical bar is sharp for any given h with 1 <= h <= 2n - 3. (C) 2010 Elsevier B.V. All rights reserved.
hypercube cycle embedding path bipancyclicity edge-fault-tolerance interconnection networks