2018/05/07 by Shu-Li Zhao, Rong-Xia Hao, Zhao, Shu-Li +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1805.02437
arxiv created 2018/05/07 · arxiv updated 2018/05/08
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)\bigcap V(Tj)=S for any i, j ∈ \1, 2, ⋯, r\ and i≠ j. For an integer k with 2≤ k≤ n, the \em 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. By proposing an algorithm to construct n-1 internally disjoint paths in Bn-1,k-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 [Applied Mathematics and Computation 274 (2016) 41-46] given by Li et al., as the bubble-sort graph Bn is the special (n,k)-bubble-sort graph for k=n-1.