A fault-free Hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges

作者：Wang Wen Qing; Chen Xie Bin^*

来源：Information Processing Letters, 2008, 107(6): 205-210.

DOI：10.1016/j.ipl.2008.02.016

• hypercube
• cycle
• edge fault tolerance
• Hamiltonian cycle
• interconnection networks

In this paper, we consider the problem of a fault-free Hamiltonian cycle passing through prescribed edges in an n-dimensional hypercube Q(n) with some faulty edges. We obtain the following result: Let n >= 2, F subset of E(Q(n)), E-0 subset of E(Q(n))\F with 1 <= vertical bar E-0 vertical bar <= 2n - 3, vertical bar F vertical bar < n - (left perpendicular vertical bar E-0 vertical bar/2right perpendicular + 1). If the subgraph induced by E-0 is a linear forest (i.e., pairwise vertex-disjoint paths), then in the graph Q,, - F all edges of EO lie on a Hamiltonian cycle.

• 出版日期2008-8-31
• 单位闽南师范大学