Conditional edge-fault hamiltonian-connectivity of restricted hypercube-like networks

Sun Yuan Hsieh, Chia Wei Lee, Chien Hsiang Huang

Research output: Contribution to journalArticle

2 Citations (Scopus)

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 (RHLn) 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(2n,4) for odd n, are all conditional (2n−7)-edge-fault hamiltonian-connected.

Original languageEnglish
Pages (from-to)314-334
Number of pages21
JournalInformation and Computation
Volume251
DOIs
Publication statusPublished - 2016 Dec 1

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'Conditional edge-fault hamiltonian-connectivity of restricted hypercube-like networks'. Together they form a unique fingerprint.

Cite this