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

Abstract

Let $S\subseteq V(G)$ and ${\kappa }_G(S)$ denote the maximum number $r$ of edge-disjoint trees $T_1,T_2,\cdots ,T_r$ in $G$ such that $V(T_i)\bigcap V(T_j)=S$ for any $i,j\in \{1,2,\cdots ,r\}$ and $i\ne j$. For an integer $k$ with $2\le k\le n$, the {\em generalized $k$-connectivity} of a graph $G$ is defined as ${\kappa }_k(G)=min\{{\kappa }_G(S)|S\subseteq V(G)$ and $|S|=k\}$. 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\le k\le n-1$. By proposing an algorithm to construct $n-1$ internally disjoint paths in $B_{n-1,k-1}$, we show that ${\kappa }_3(B_{n,k})=n-2$ for $2\le k\le 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 $et$ $al.$, as the bubble-sort graph $B_n$ is the special $(n,k)$-bubble-sort graph for $k=n-1$.