The generalized connectivity of (n,k)-bubble-sort graphs

Abstract: Let

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

and

k a p p a_{G} (S)

denote the maximum number

r

of edge-disjoint trees

T_{1}, T_{2}, c d o t s, T_{r}

in

G

such that

for any

i, j i n 1, 2, c d o t s, r

and

i e q j

. For an integer

k

with

2 l e q k l e q n

, the {em generalized

k

-connectivity} of a graph

G

is defined as

and

. The generalized

k

-connectivity is a generalization of the traditional connectivity. In this paper, the generalized

3

-connectivity of the

(n, k)

-bubble-sort graph

B_{n, k}

is studied for

2 l e q k l e q n - 1

. By proposing an algorithm to construct

n - 1

internally disjoint paths in

B_{n - 1, k - 1}

, we show that

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

for

2 l e q k l e q n - 1

, which generalizes the known result about the bubble-sort graph

B_{n}

[Applied Mathematics and Computation 274 (2016) 41-46] given by Li

e t

a l .

, as the bubble-sort graph

B_{n}

is the special

(n, k)

-bubble-sort graph for

k = n - 1

.

This page was built for publication: The generalized connectivity of $(n,k)$-bubble-sort graphs