×

Pancyclicity of restricted hypercube-like networks under the conditional fault model. (English) Zbl 1207.05106

Summary: 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(2^{n},4)\) for odd \(n, n\)-dimensional crossed cubes, and \(n\)-dimensional twisted cubes for odd \(n\), are all conditional \((2n-5)\)-edge-fault pancyclic.

MSC:

05C38 Paths and cycles
68R10 Graph theory (including graph drawing) in computer science
94C15 Applications of graph theory to circuits and networks
PDFBibTeX XMLCite
Full Text: DOI