Fault-free cycles passing through prescribed a linear forest in a hypercube with faulty edges

作者：Yao Xiao Pan; Chen Xie Bin^*

来源：Ars Combinatoria, 2014, 116: 213-223.

• Hypercube
• Cycle embedding
• Hamiltonian cycle
• Fault tolerance
• Interconnection network

Chen considered the problem of fault-free cycles passing through prescribed a linear forest in an n-dimensional hypercube Q(n) with some faulty edges and obtained the following result: Let n > h >= 2, F subset of E(Q(n)) with vertical bar F vertical bar < n - h, and E-0 subset of E(Q(n))\F with vertical bar E-0 vertical bar = h. If the subgraph induced by E-0 is a linear forest, then in the graph Q(n) - F all edges of E-0 lie on a cycle of every even length l with 2(h-1)(n + 1 - h) + 2(h - 1) <= l < 2(n). In this paper, above result is improved as follows: under the same condition in Q(n) - F all edges of E-0 lie on a cycle of every even length l with 2(h - 1)n - 6(h - 2) <= l < 2(n).

• 出版日期2014-7
• 单位闽南师范大学