Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10333906 | Theoretical Computer Science | 2011 | 15 Pages |
Abstract
It is well known that the k-ary n-cube has been one of the most efficient interconnection networks for distributed-memory parallel systems. A k-ary n-cube is bipartite if and only if k is even. In this paper, we consider the faulty k-ary n-cube with even kâ¥4 and nâ¥2 such that each vertex of the k-ary n-cube is incident with at least two healthy edges. Based on this requirement, we prove that the k-ary n-cube contains a hamiltonian path joining every pair of vertices which are in different parts, even if it has up to 4nâ6 edge faults.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Shiying Wang, Shurong Zhang,