The generalized 3-connectivity of star graphs and bubble-sort graphs

The generalized 3-connectivity of star graphs and bubble-sort graphs

0.00 Avg rating0 Votes
Article ID: iaor201530779
Volume: 274
Start Page Number: 41
End Page Number: 46
Publication Date: Feb 2016
Journal: Applied Mathematics and Computation
Authors: , ,
Keywords: optimization, networks, combinatorial optimization
Abstract:

For SG, let K(S) denote the maximum number r of edge‐disjoint trees T 1 , T 2 , , T r equ1 in G such that V ( T i ) n V ( T j ) = S equ2 for any i , j { 1 , 2 , , r } equ3 and ij. For every 2 ≤ kn, the generalized kconnectivity of G Kk (G) is defined as the minimum K(S) over all k‐subsets S of vertices, i.e., K k ( G ) = equ4 min { K ( S ) | S V ( G ) and | S | = k } equ5. Clearly, K 2(G) corresponds to the traditional connectivity of G. The generalized k‐connectivity can serve for measuring the capability of a network G to connect any k vertices in G. Cayley graphs have been used extensively to design interconnection networks. In this paper, we restrict our attention to two classes of Cayley graphs, the star graphs Sn and the bubble‐sort graphs Bn , and investigate the generalized 3‐connectivity of Sn and Bn . We show that K 3 ( S n ) = n 2 equ6 and K 3 ( B n ) = n 2 equ7.

Reviews

Required fields are marked *. Your email address will not be published.