The Generalized 4-Connectivity of Bubble-Sort Graphs

For [Formula: see text] with [Formula: see text], let [Formula: see text] denote the maximum number of edge disjoint trees connecting [Formula: see text] in [Formula: see text]. For [Formula: see text], the generalized [Formula: see text]-connectivity [Formula: see text] of an [Formula: see text]-vertex connected graph [Formula: see text] is defined to be [Formula: see text]. The generalized [Formula: see text]-connectivity can serve for measuring the fault tolerance of an interconnection network. The bubble-sort graph [Formula: see text] for [Formula: see text] is a Cayley graph over the symmetric group of permutations on [Formula: see text] generated by transpositions from the set [Formula: see text]. In this paper, we show that for the bubble-sort graphs [Formula: see text] with [Formula: see text], [Formula: see text].