Strong Menger Connectivity on the Bubble-sort Graphs

Abstract

Interconnection networks have been widely dis- cussed in recent days, and usually represented as undirected graphs. One of the most important prop- erties of graphs is the connectivity, which is defined as the minimum number of vertices removed from a graph resulting in a disconnected graph or a graph containing a single isolated vertex. A famous theo- rem by Menger [4] pointed out the equivalence of the minimum size of an x, y-cut and the maximum num- ber of pairwise internally disjoint x, y-paths for some nonadjacent vertices x, y in a graph. After that, Oh and Chen [5] extended this concept to introduce the property called strongly Menger connectivity, which describes that, with some faulty vertices, the num- ber of x, y-paths is the minimum remaining degree of them. In this paper, we focus on a recursively constructed interconnection network, the bubble-sort graph. We prove that in an n-dimensional bubble- sort graph Bn with at most n − 3 faulty vertices, it is strongly Menger-connected.