The generalized 4-connectivity of bubble-sort graphs

Abstract: For

S s u b s e t e q V (G)

with

| S | g e 2

, let

k a p p a_{G} (S)

denote the maximum number of internally disjoint trees connecting

S

in

G

. For

2 l e k l e n

, the generalized

k

-connectivity

k a p p a_{k} (G)

of an

n

-vertex connected graph

G

is defined to be

k a p p a_{k} (G) = m i n k a p p a_{G} (S) : S i n V (G) m b o x a n d | S | = k

. The generalized

k

-connectivity can serve for measuring the fault tolerance of an interconnection network. The bubble-sort graph

B_{n}

for

n g e 2

is a Cayley graph over the symmetric group of permutations on

[n]

generated by transpositions from the set

[1, 2], [2, 3], d o t s, [n - 1, n]

. In this paper, we show that for the bubble-sort graphs

B_{n}

with

n g e 3

,

k a p p a_{4} (B_{n}) = n - 2

.

This page was built for publication: The generalized $4$-connectivity of bubble-sort graphs