The Generalized Connectivity of Data Center Networks

The generalized k-connectivity of a graph G is a parameter that can measure the reliability of a network G to connect any k vertices in G, which is a generalization of traditional connectivity. Let S subset of V(G) and kappa(G)(S) denote the maximum number r of edge-disjoint trees T-1, T-2, . . . T-r in G such that V(T-i) boolean AND V(T-j) = S for any i,j is an element of {1, 2, ... , r} and i not equal j. For an integer k with 2 <= k <= n, the generalized k-connectivity of a graph G is defined as kappa(k)(G) = min{kappa(G)(S) subset of V(G) and vertical bar S vertical bar = k}. Data centers are essential to the business of companies such as Google, Amazon, Facebook and Microsoft et al. Based on data centers, the data center networks D-k,D-n, introduced by Guo et al. in 2008, have many desirable properties. In this paper, we study the generalized 3-connectivity of D-k,D-n, and show that kappa(3)(D-k,D- n) = n + k - 2 for k >= 0 and n >= 3.