Article ID Journal Published Year Pages File Type
428330 Information Processing Letters 2007 5 Pages PDF
Abstract

A bipartite graph is vertex-bipancyclic (respectively, edge-bipancyclic) if every vertex (respectively, edge) lies in a cycle of every even length from 4 to |V(G)| inclusive. It is easy to see that every connected edge-bipancyclic graph is vertex-bipancyclic. An n-dimensional hypercube, or n-cube denoted by Qn, is well known as bipartite and one of the most efficient networks for parallel computation. In this paper, we study a stronger bipancyclicity of hypercubes. We prove that every n-dimensional hypercube is (2n−4)-path-bipancyclic for n⩾3. That is, for any path P of length k with 1⩽k⩽2n−4 and any integer l with max{2,k}⩽l⩽2n−1, an even cycle C of length 2l can be found in Qn such that the path P is included in C for n⩾3.

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