On reliability of the folded hypercubes in terms of the extra edge-connectivity

International audienceFor a graph $G$ and a non-negative integer $g$, the $g$-extra edge connectivity of $G$ is the minimum cardinality of a set of edges in $G$, if it exists, whose deletion disconnects $G$ and each remaining component will have at least $g$ vertices. The extra edge-connectivity is an important parameters for the reliability evaluation of interconnection networks. In this paper, we explore $g$-extra-edge-connectivity $(\lambda_g(FQ_n))$ of the folded hypercube $FQ_n$ for $g\leq n$ (denote $g$ by $\sum_{i=0}^s2^{t_i}$, where $t_0=[\log_2g]$ and $t_i=[\log_2(g−\sum_{r=0}^{i-1}2^{t_r})])$ . We show that $\lambda_g(FQ_n)=g(n+1)−(\sum_{i=0}^st_i2^{t_i}+ \sum_{i=0}^s2\cdot i \cdot 2^{t_i})$ for $n\geq 6$. This result generalizes the previous results by Zhu et al. (2007) for $\lambda_3(FQ_n)$, and by Hsieh and Tsai (in press) for $\lambda_4(FQ_n)$, and so on