The Generalized Three-Connectivity of Two Kinds of Cayley Graphs

摘要

Let $S subseteq V (G)$ and $kappa_{G}(S)$ denote the maximum number $r$ of edge-disjoint trees $T_1, T_2,ldots, T_r$ in G such that $V (T_i) cap V (T_j) =S$ for any $i,j in { 1, 2, ldots, r}$ and $i eq j$. For an integer k with $2 leq k leq n$, the generalized k-connectivity of a graph G is defined as $kappa_k (G) = min {kappa_{G} (S) ert S subseteq V (G)$ and $ert S ert = 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 $CT_n$ and $WG_n$, respectively. We study the generalized 3-connectivity of the two kinds of graphs and show that $kappa_{3} (CT_n) = {n(n-1) over 2} - 1$ and $kappa_3 (WG_n) = 2n - 3$ for $n geq 3$.