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

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. (C) 2018 Elsevier B.V. All rights reserved.