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

Abstract

This paper studies the edge-fault-tolerant strong Menger edge connectivity of $ n $-dimensional bubble-sort graph $ B_{n} $. We give the values of faulty edges that $ B_{n} $ can tolerant when $ B_{n} $ is strongly Menger edge connected under two conditions. When there are $ (n-3) $ faulty edges removed from $ B_{n} $, the $ B_{n} $ network is still working and it is strongly Menger edge connected. When the condition of any vertex in $ B_{n} $ has at least two neighbors is imposed, the number of faulty edges that can removed from $ B_{n} $ is $ (2n-6) $ when $ B_{n} $ is also strongly Menger edge connected. And two special cases are used to illustrate the correctness of the conclusions. The conclusions can help improve the reliability of the interconnection networks.

Keywords

• edge-disjoint paths
• fault-tolerant
• strong menger edge connectivity
• bubble-sort graph