## Abstract

The k-ary n-cube, denoted by Q_{n}^{k}, is one of the most important interconnection networks for parallel computing. In this paper, we consider the problem of embedding cycles and paths into faulty 3-ary n-cubes. Let F be a set of faulty nodes and/or edges, and n ≥ 2. We show that when | F | ≤ 2 n - 2, there exists a cycle of any length from 3 to | V (Q_{n}^{3} - F) | in Q_{n}^{3} - F. We also prove that when | F | ≤ 2 n - 3, there exists a path of any length from 2 n - 1 to | V (Q_{n}^{3} - F) | - 1 between two arbitrary nodes in Q_{n}^{3} - F. Since the k-ary n-cube is regular of degree 2 n, the fault-tolerant degrees 2 n - 2 and 2 n - 3 are optimal.

Original language | English |
---|---|

Pages (from-to) | 198-208 |

Number of pages | 11 |

Journal | Information Sciences |

Volume | 180 |

Issue number | 1 |

DOIs | |

State | Published - 2 Jan 2010 |

## Keywords

- Cycle
- Embedding
- Fault-tolerance
- Interconnection networks
- Path
- k-Ary n-cube