A lower bound on the number of Hamiltonian cycles through a prescribed edge in a crossed cube

作者：Chen Jheng Cheng; Lai Chia Jui; Tsai Chang Hsiung^*; Lai Pao Lien

来源：Applied Mathematics and Computation, 2013, 219(19): 9885-9892.

DOI：10.1016/j.amc.2013.03.128

• Interconnection network
• Linear-time algorithm
• Reflected sequence
• Hamiltonian
• Crossed cubes
• Prescribed edge

The crossed cube proposed by Efe is one of the most notable variations of the hypercube, but some properties of the former are superior to those of the latter. For example, the diameter of the crossed cube is almost the half that of the hypercube. In this paper, we consider the problem of embedding a Hamiltonian cycle passing through a prescribed edge in crossed cubes. A concept termed the cycle pattern is used to construct a linear algorithm for embedding a structural Hamiltonian cycle so the cycle passes through an arbitrary given edge in the crossed cube. Further, we give the necessary and sufficient conditions for determining what kind of permutation generates a Hamiltonian cycle pattern of the crossed cube. As a result, we obtain a lower bound for the number of Hamiltonian cycles through a given edge in an n-dimensional crossed cube. Our work extends some recently obtained results.

• 出版日期2013-6-1
• 单位东华大学