The Generalized Connectivity of (n, k)-Bubble-Sort Graphs. (20th October 2018) - Zhao, Shu-Li; Hao, Rong-Xia; Wu, Lidong
Abstract: Let S ⊆ V ( G ) and κ G ( S ) denote the maximum number r of edge-disjoint trees T 1, T 2, …, T r in G such that V ( T i ) ∩ V ( T j ) = 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 B n, k is studied for 2 ≤ k ≤ n − 1 . We show that κ 3 ( B n, k ) = n − 2 for 2 ≤ k ≤ n − 1, which generalizes the known result about the bubble-sort graph B n (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 B n is the special ( n, k ) -bubble-sort graph for k = n − 1 .