Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes

Ashir, Y.A.; Stewart, I.A.

doi:10.1137/s0895480196311183

Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes

Ashir, Y.A.; Stewart, I.A.

Authors

Y.A. Ashir

Professor Iain Stewart i.a.stewart@durham.ac.uk
Professor

Abstract

We consider the fault-tolerant capabilities of networks of processors whose underlying topology is that of the k-ary n-cube $Q_n^k$, where k > 2 and n > 1. In particular, given a copy of $Q_n^k$ where some of the inter-processor links may be faulty but where every processor is incident with at least two healthy links, we show that if the number of faults is at most 4n-5 then $Q_n^k$ still contains a Hamiltonian circuit; but that there are situations where the number of faults is 4n-4 (and every processor is incident with at least two healthy links) and no Hamiltonian circuit exists. We also remark that given a faulty $Q_n^k$, the problem of deciding whether there exists a Hamiltonian circuit is NP-complete.

Citation

Ashir, Y., & Stewart, I. (2002). Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes. SIAM Journal on Discrete Mathematics, 15(3), 317-328. https://doi.org/10.1137/s0895480196311183

Journal Article Type	Article
Publication Date	2002
Deposit Date	Oct 8, 2008
Publicly Available Date	Oct 8, 2008
Journal	SIAM Journal on Discrete Mathematics
Print ISSN	0895-4801
Electronic ISSN	1095-7146
Publisher	Society for Industrial and Applied Mathematics
Peer Reviewed	Peer Reviewed
Volume	15
Issue	3
Pages	317-328
DOI	https://doi.org/10.1137/s0895480196311183
Keywords	Interconnection networks, Fault-tolerance, NP-completeness.
Publisher URL	http://epubs.siam.org/SIDMA/volume-15/art_31118.html