The Generalized Connectivity of (n, k)-Bubble-Sort Graphs. (20th October 2018)

• Record Type: Journal Article
• Authors: Zhao, Shu-Li; Hao, Rong-Xia; Wu, Lidong
• Is Part Of: Computer journal. Volume 62:Number 9(2019)
• Page Start: 1277
• Page End: 1283
• Publication Date: 2018-10-20
• Subjects: generalized connectivity -- fault-tolerance -- interconnection network -- (n, k)-bubble-sort graph; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxy106
• Languages: English
• ISSNs: 0010-4620

Abstract

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 .