## Abstract

A graph G is considered conditional k-edge-fault hamiltonian-connected if, after k faulty edges are removed from G, under the assumption that each node is incident to at least three fault-free edges, a hamiltonian path exists between any two distinct nodes in the resulting graph. This paper focuses on the conditional edge-fault hamiltonian-connectivity of a wide class of interconnection networks called restricted hypercube-like networks (RHLs). An n-dimensional RHL (RHL_{n}) is proved to be conditional (2n−7)-edge-fault hamiltonian-connected for n≥5. The technical theorem proposed in this paper is then applied to show that several multiprocessor systems, including n-dimensional crossed cubes, n-dimensional twisted cubes for odd n, n-dimensional locally twisted cubes, n-dimensional generalized twisted cubes, n-dimensional Möbius cubes, and recursive circulants G(2^{n},4) for odd n, are all conditional (2n−7)-edge-fault hamiltonian-connected.

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

Pages (from-to) | 314-334 |

Number of pages | 21 |

Journal | Information and Computation |

Volume | 251 |

DOIs | |

Publication status | Published - 2016 Dec 1 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics