Linearly many faults in dual-cube-like networks

The dual cubes were introduced as a better interconnection network than the hypercubes for large scale distributed memory multiprocessors. In this paper we introduce a generalization of these networks, called dual-cube-like networks, which preserve the basic structure of dual cubes and retain many of its topological properties. We investigate structural properties of these networks beyond simple measures such as connectivity. We prove that if up to kn - k(k+1)/2 vertices are deleted from a dual-cube-like n-regular network, then the resulting graph will either be connected or will have a large component and small components having at most k - 1 vertices in total, and this result is sharp for k <= n. As an application, we derive additional results such as the cyclic vertex-connectivity and the restricted vertex-connectivity of these networks. (C) 2012 Elsevier B.V. All rights reserved.