Hamiltonian paths and cycles passing through a prescribed path in hypercubes

Assume that P is any path in a bipartite graph G of length k with 2 <= k <= h, G is said to be h-path bipancyclic if there exists a cycle C in G of every even length from 2k to vertical bar V(G)vertical bar such that P lies in C. In this paper, the following result is obtained: The n-dimensional hypercube Q(n) with n >= 3 is (2n - 3)-path bipancyclic but is not (2n - 2)-path bipancyclic, moreover, a path P of length k with 2 <= k <= 2n - 3 lies in a cycle of length 2k - 2 if and only if P contains two edges of the same dimension. In order to prove the above result we first show that any path of length at most 2n - 1 is a subpath of a Hamiltonian path in Q(n) with n >= 2, moreover, the upper bound 2n - 1 is sharp when n >= 4. (C) 2009 Elsevier B.V. All rights reserved.