The Restricted Connectivity of Bubble-Sort Star Graphs

The restricted connectivity is a conditional connectivity as an improvement of the classical connectivity to measure the fault-tolerance of interconnection networks. For a graph [Formula: see text], its [Formula: see text]-restricted connectivity [Formula: see text] such that [Formula: see text] is disconnected and each vertex in [Formula: see text] with degree at least [Formula: see text]. The [Formula: see text]-dimensional bubble-sort star graph [Formula: see text] is an interconnection network, which possesses many favourable properties including regularity, recursive construction, vertex symmetry, and high fault tolerance. In this paper, we show that [Formula: see text] for [Formula: see text], which is an improvement of [Formula: see text] for [Formula: see text] [Discrete Appl. Math. 217 (2017) 691–706.].