Pancyclicity of restricted hypercube-like networks under the conditional fault model

Sun-Yuan Hsieh, Chia Wei Lee

Research output: Contribution to journalArticlepeer-review

54 Citations (Scopus)

Abstract

A graph G is said to be conditional k-edge-fault pancyclic if after removing k faulty edges from G, under the assumption that each node is incident to at least two fault-free edges, the resulting graph contains a cycle of every length from its girth to |V (G)|. In this paper, we consider the common properties of a wide class of interconnection networks, called restricted hypercube-like networks, from which their conditional edge-fault pancyclicity can be determined. We then apply our technical theorems to show that several multiprocessor systems, including n-dimensional locally twisted cubes, n-dimensional generalized twisted cubes, recursive circulants G(2n, 4) for odd n, n-dimensional crossed cubes, and n-dimensional twisted cubes for odd n, are all conditional (2n-5)-edge-fault pancyclic.

Original languageEnglish
Pages (from-to)2100-2119
Number of pages20
JournalSIAM Journal on Discrete Mathematics
Volume23
Issue number4
DOIs
Publication statusPublished - 2009 Dec 1

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Pancyclicity of restricted hypercube-like networks under the conditional fault model'. Together they form a unique fingerprint.

Cite this