Article ID Journal Published Year Pages File Type
428131 Information Processing Letters 2009 5 Pages PDF
Abstract

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 |V(G)| such that P lies in C. Based on Lemma 5, the authors of [C.-H. Tsai, S.-Y. Jiang, Path bipancyclicity of hypercubes, Inform. Process. Lett. 101 (2007) 93–97] showed that the n-cube Qn with n⩾3 is (2n−4)-path bipancyclicity. In this paper, counterexamples to the lemma are given, therefore, their proof fails. And we show the following result: The n-cube Qn with n⩾3 is (2n−4)-path bipancyclicity but is not (2n−2)-path bipancyclicity, moreover, and a path P of length k with 2⩽k⩽2n−4 lies in a cycle of length 2k−2 if and only if P contains two edges of dimension i for some i, 1⩽i⩽n. We conjecture that if 2n−4 is replaced by 2n−3, then the above result also holds.

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