A Note on the Component (Extra) Edge Connectivity of the Cartesian Powers of Regular Multiprocessor Systems
Liqiong Xu, Shuming Zhou · IEEE Transactions on Reliability · 2025
Reliability assessment of multiprocessor systems presents the theoretical foundation for the layout and optimization of multiprocessor systems. The$h$-extra edge-connectivity$\lambda _{h}$and the$k$-component edge-connectivity$c\lambda _{k}$, as extensions of the classical edge connectivity, are two precise metrics for the measurement of the reliability of multiprocessor systems. For multiprocessor systems, determining$c\lambda _{k}$and$\lambda _{k}$of a large$k$is still difficult. Let$\delta _{G}(0)=0$and$\delta _{G}(i)=\frac{1}{2}(\text{ex}_{i+1}(G)-\text{ex}_{i}(G))$for$i\in \lbrace 1, \ldots, |G|-1\rbrace$, where$\text{ex}_{i}(G)={\mathrm{max}}\lbrace 2|E(G[S])|: S\subseteq V(G), |S|=i \rbrace$. In this article, we obtain$c\lambda _{k}$and$\lambda _{h}$of the Cartesian powers of the$d$-regular graphs for which the lexicographic order yields an optimal order and$\delta _{G}(i)\leq \frac{d}{2}$for$i=0, 1, \ldots, \lfloor \frac{|G|-1}{2}\rfloor$. Our result improves some previous results about$c\lambda _{k}$of Hamming graphs by Yang et al. (2023), and$\lambda _{h}$of the Cartesian powers of the complete graph$K_{4}$by Tian et al. (2022).