Embedding fault-free hamiltonian paths with prescribed linear forests into faulty ternary n-cubes

作者：Yang, Yuxing^*; Li, Jing; Wang, Shiying

来源：Theoretical Computer Science, 2019, 767: 1-15.

DOI：10.1016/j.tcs.2018.09.020

• Multiprocessor systems
• Interconnection networks
• Fault tolerance
• Prescribed linear forests
• Hamiltonian paths

The k-ary n-cube is an important underlying topology for large-scale multiprocessor systems. A linear forest in a graph is a subgraph each component of which is a path. In this paper, we investigate the problem of embedding hamiltonian paths passing through a prescribed linear forest in ternary n-cubes with faulty edges. Given a faulty edge set F with at most 2n - 3 edges and a linear forest L with at most 2n - 3 - vertical bar F vertical bar edges, for two distinct vertices in the ternary n-cube, we show that the ternary n-cube admits a fault-free hamiltonian path between u and v passing through L if and only if none of the paths in L has u or v as internal vertices or both of them as end-vertices.

• 出版日期2019-5-3
• 单位河南师范大学; 太原科技大学