The Arc-Connectivity and Restricted Arc-Connectivity of the Unidirectional Bubble-Sort Star Graphs

Let [Formula: see text] be a digraph, an arc set [Formula: see text] in [Formula: see text] is an arc-cut if [Formula: see text] is not strong. The arc-connectivity, denoted by [Formula: see text], of [Formula: see text] is the minimum cardinality of all arc-cuts of [Formula: see text]. Furthermore, if [Formula: see text] is an arc-cut and [Formula: see text] has a strong component [Formula: see text] with [Formula: see text] and [Formula: see text] contains an arc, then we call [Formula: see text] is a restricted arc-cut of [Formula: see text]. The restricted arc-connectivity, denoted by [Formula: see text], is the minimum cardinality over all restricted arc-cuts [Formula: see text] in [Formula: see text]. In this paper, we first construct a novel network from the bubble-sort star graph [Formula: see text] by Day–Tripathi orientation (named the [Formula: see text]-dimensional unidirectional bubble-sort star graph and denoted by [Formula: see text]), and then show that the arc-connectivity of the [Formula: see text]-dimensional unidirectional bubble-sort star graph is [Formula: see text]. The restricted arc-connectivity of the [Formula: see text]-dimensional unidirectional bubble-sort star graph is also completely determined ([Formula: see text]).