The bipanpositionable bipancyclic property of the hypercube

Abstract

A bipartite graph is bipancyclic if it contains a cycle of every even length from 4 to vertical bar V(G)vertical bar inclusive. A hamiltonian bipartite graph G is bipanpositionable if, for any two different vertices x and y, there exists a hamiltonian cycle C of G such that d(c)(x, y) = k for any integer k with d(G)(x, y) <= k <= vertical bar V(G)vertical bar/2 and (k - d(G)(x, y)) being even. A bipartite graph G is k-cycle bipanpositionable if, for any two different vertices x and y, there exists a cycle of G with d(C)(x, y) = l and vertical bar V(C)vertical bar = k for any integer l with d(G)(x, y) <= l <= k/2 and (l - d(G)(x, y)) being even. A bipartite graph G is bipanpositionable bipancyclic if G is k-cycle bipanpositionable for every even integer k, 4 <= k <= vertical bar V(G)vertical bar. We prove that the hypercube Q(n) is bipanpositionable bipancyclic for n >= 2. (C) 2009 Elsevier Ltd. All rights reserved.