On the bipanpositionable bipanconnectedness of hypercubes

Abstract

A bipartite graph G is bipanconnected if, for any two distinct vertices x and y of G, it contains an vertical bar x,y vertical bar-path of length l for each integer l satisfying d(G)(x, y) <= l <= vertical bar V(G)vertical bar - 1 and 2 vertical bar(l - d(G)(x, y)), where d(G)(x, y) denotes the distance between vertices x and y in G and V(G) denotes the vertex set of G. We say a bipartite graph G is bipanpositionably bipanconnected if, for any two distinct vertices x and y of G and for any vertex z is an element of V(G) - (x, y), it contains a path P(l,k) of length l Such that x is the beginning vertex of P(l,k), z is the (k + 1)-th vertex of P(l,k), and y is the ending vertex of P(l,k) for each integer l satisfying d(G)(x, z) + d(G)(y, z) <= l <= vertical bar V(G)vertical bar - 1 and 2 vertical bar(l - d(G)(x, z) - d(G)(y, z)) and for each integer k satisfying d(G)(x, z) <= k <= l -d(G)(y, z) and 2 vertical bar(k - d(G)(x, z)). In this paper, we prove that an n-cube is bipanpositionably bipanconnected if n >= 4. As a consequence, many properties of hypercubes, such as bipancyclicity, bipanconnectedness, bipanpositionable Hamiltonicity, etc., follow directly from our result. (C) 2008 Elsevier B.V. All rights reserved.