The Generalized Three-Connectivity of Two Kinds of Cayley Graphs

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 (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)vertical bar S subset of V (G) and vertical bar S vertical bar = k}. The generalized k-connectivity is a generalization of traditional connectivity. In this paper, we focus on the Cayley graph generated by complete graphs and the Cayley graph generated by wheel graphs, denoted by CTn and WG(n), respectively. We study the generalized 3-connectivity of the two kinds of graphs and show that kappa(3)(CTn) = n(n - 1)/2 - 1 and kappa(3)(WG(n)) = 2n - 3 for n >= 3.