Strongly Menger Connectedness of a Class of Recursive Networks

According to Menger's theorem, connectivity and edge connectivity are closely related to node-disjoint paths and edge-disjoint paths, respectively. Node- and edge-disjoint paths can keep the effective transmission of information and confidentiality. Therefore, node-disjoint paths and edge-disjoint paths are two important parameters to measure the reliability of a network. For a faulty node (resp. edge) set $S\subset V$ (resp. $S\subset E$), a connected graph $G=(V,E)$ is $S$-strongly Menger-node-connected (resp. Menger-edge-connected) if any two distinct nodes $x$ and $y$ in $G-S$ are connected by $\min \{\deg _{G-S}(x),\deg _{G-S}(y)\}$ internally node-disjoint (resp. edge-disjoint) paths in $G-S$, where $\deg _{G-S}(x)$ and $\deg _{G-S}(y)$ are the degrees of $x$ and $y$ in $G-S$, respectively. And most of the previous studies are based on networks that are triangle-free. In this paper, we consider the strongly Menger (edge) connectedness of a class of $r$-dimensional recursive networks RNCG $G_{r}$ with triangles. Moreover, we show that $G_{r}$ is $(rl-l-1)$-strongly Menger-node-connected. And then we show that $G_{r}$ is $[k+(r-1)l-2]$-strongly Menger-edge-connected of order 1 and $[2k+2(r-1)l-6]$-strongly Menger-edge-connected of order 2. Since the class of $r$-dimensional recursive networks RNCG $G_{r}$ includes not only data center networks DCell and generalized DCell but also interconnection network dragonfly, etc., all the results are appropriate for these networks.

Automated summary

This paper studies the strongly Menger connectedness of r-dimensional recursive networks with triangles and provides related results.