Generalized Measures of Fault Tolerance in Exchanged Hypercubes

Abstract

The exchanged hypercube $EH(s,t)$, proposed by Loh {\it et al.} [The exchanged hypercube, IEEE Transactions on Parallel and Distributed Systems 16 (9) (2005) 866-874], is obtained by removing edges from a hypercube $Q_{s+t+1}$. This paper considers a kind of generalized measures ${\kappa }^{(h)}$ and ${\lambda }^{(h)}$ of fault tolerance in $EH(s,t)$ with $1⩽s⩽t$ and determines ${\kappa }^{(h)}(EH(s,t))={\lambda }^{(h)}(EH(s,t))=2^h(s+1-h)$ for any $h$ with $0⩽h⩽s$. The results show that at least $2^h(s+1-h)$ vertices (resp. $2^h(s+1-h)$ edges) of $EH(s,t)$ have to be removed to get a disconnected graph that contains no vertices of degree less than $h$, and generalizes some known results.

References in corpus (1)

• Generalized Measures of Fault Tolerance in (n,k)-star Graphs