Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428330 | Information Processing Letters | 2007 | 5 Pages |
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