Edge-Fault Tolerance of Hypercube-like Networks

Abstract

This paper considers a kind of generalized measure ${\lambda }_s^{(h)}$ of fault tolerance in a hypercube-like graph $G_n$ which contain several well-known interconnection networks such as hypercubes, varietal hypercubes, twisted cubes, crossed cubes and Möbius cubes, and proves ${\lambda }_s^{(h)}(G_n)=2^h(n-h)$ for any $h$ with $0⩽h⩽n-1$ by the induction on $n$ and a new technique. This result shows that at least $2^h(n-h)$ edges of $G_n$ have to be removed to get a disconnected graph that contains no vertices of degree less than $h$. Compared with previous results, this result enhances fault-tolerant ability of the above-mentioned networks theoretically.