Component edge connectivity of the folded hypercube

Abstract

The $g$-component edge connectivity $c{\lambda }_g(G)$ of a non-complete graph $G$ is the minimum number of edges whose deletion results in a graph with at least $g$ components. In this paper, we determine the component edge connectivity of the folded hypercube $c{\lambda }_{g+1}(F{Q}_n)=(n+1)g-(\sum _{i=0}^s{t}_i{2}^{t_i-1}+\sum _{i=0}^{s}i\cdot 2^{t_i})$ for $g\le 2^{[\frac{n+1}{2}]}$ and $n\ge 5$, where $g$ be a positive integer and $g=\sum _{i=0}^s{2}^{t_i}$ be the decomposition of $g$ such that $t_0=[{\log }_{2}g],$ and $t_i=[{\log }_2(g-\sum _{r=0}^{i-1}{2}^{t_r})]$ for $i\ge 1$.

The work was included in the MS thesis of the first author in [On the component connectiviy of hypercubes and folded hypercubes, MS Thesis at Taiyuan University of Technology, 2017]