3-path-connectivity of bubble-sort star graphs

Abstract

Let $G$ be a simple connected graph with vertex set $V(G)$ and edge set $E(G)$. Let $T$ be a subset of $V(G)$ with cardinality $|T|\ge 2$. A path connecting all vertices of $T$ is called a $T$-path of $G$. Two $T$-paths $P_i$ and $P_j$ are said to be internally disjoint if $V(P_i)\cap V(P_j)=T$ and $E(P_i)\cap E(P_j)=\varnothing$. Denote by $\ddot{I}{€}_G(T)$ the maximum number of internally disjoint $T$- paths in G. Then for an integer $\ell$ with $\ell \ge 2$, the $\ell$-path-connectivity $\ddot{I}{€}_{\ell }(G)$ of $G$ is formulated as $\min \{\ddot{I}{€}_G(T)|T\subseteq V(G)$ and $|T|=\ell \}$. In this paper, we study the $3$-path-connectivity of $n$-dimensional bubble-sort star graph $B{S}_n$. By deeply analyzing the structure of $B{S}_n$, we show that $\ddot{I}{€}_3(B{S}_n)=\lfloor \frac{3n}{2}\rfloor -3$, for any $n\ge 3$.