The Generalized Connectivity of (n,k)-Bubble-Sort Graphs
Shu-Li Zhao, Rong‐Xia Hao, Lidong Wu · The Computer Journal · 2018
Let S⊆V(G) and κG(S) denote the maximum number r of edge-disjoint trees T1,T2,…,Tr in G such that V(Ti)∩V(Tj)=S for any i,j∈{1,2,…,r} and i≠j. For an integer k with 2≤k≤n, the generalized k-connectivity of a graph G is defined as κk(G)=min{κG(S)|S⊆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 Bn,k is studied for 2≤k≤n−1. We show that κ3(Bn,k)=n−2 for 2≤k≤n−1, which generalizes the known result about the bubble-sort graph Bn (Li, S., Tu, J. and Yu, C. (2016) The generalized 3-connectivity of star graphs and bubble-sort graphs. Appl. Math. Comput., 274, 41–46), as the bubble-sort graph Bn is the special (n,k)-bubble-sort graph for k=n−1.