Edge-fault-tolerant strong Menger edge connectivity of bubble-sort star graphs

Abstract

The connectivity and edge connectivity of interconnection network determine the fault tolerance of the network. An interconnection network is usually viewed as a connected graph, where vertex corresponds processor and edge corresponds link between two distinct processors. Given a connected graph $G$ with vertex set $V(G)$ and edge set $E(G)$, if for any two distinct vertices $u,v\in V(G)$, there exist $\min \{d_G(u),d_G(v)\}$ edge-disjoint paths between $u$ and $v$, then $G$ is strongly Menger edge connected. Let $m$ be an integer with $m\ge 1$. If $G-F_e$ remains strongly Menger edge connected for any $F_e\subseteq E(G)$ with $|F_e|\le m$, then $G$ is $m$-edge-fault-tolerant strongly Menger edge connected. If $G-F_e$ is strongly Menger edge connected for any $F_e\subseteq E(G)$ with $|F_e|\le m$ and $\delta (G-F_e)\ge 2$, then $G$ is $m$-conditional edge-fault-tolerant strongly Menger edge connected. In this paper, we consider the $n$-dimensional bubble-sort star graph $B{S}_n$. We show that $B{S}_n$ is $(2n-5)$-edge-fault-tolerant strongly Menger edge connected for $n\ge 3$ and $(6n-17)$-conditional edge-fault-tolerant strongly Menger edge connected for $n\ge 4$. Moreover, we give some examples to show that our results are optimal.

19 pages, 3 figures