Article ID Journal Published Year Pages File Type
429076 Information Processing Letters 2010 5 Pages PDF
Abstract

Let Qn denote an n-dimensional hypercube with n⩾2, P be a path of length h in Qn and F⊂E(Qn)\E(P). Recently, Tsai proved that if 1⩽h⩽n−1 and |F|⩽n−1−h, then in the graph Qn−F the path P lies on a cycle of every even length from 2h+2 to n2, and P also lies on a cycle of length 2h if |F|⩽h−2. In this paper, we show that if 1⩽h⩽2n−3 and |F|⩽n−2−⌊h/2⌋, then in Qn−F the path P lies on a cycle of every even length from 2h+2 to n2, 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 |F∩E(Qh)|⩽h−2, where Qh 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−⌊h/2⌋ of |F| is sharp for any given h with 1⩽h⩽2n−3.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics