The generalized connectivity of some regular graphs

Abstract

The generalized $k$-connectivity ${\kappa }_k(G)$ 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 proved to be NP-complete for a general graph $G$. Let $S\subseteq V(G)$ and ${\kappa }_G(S)$ denote the maximum number $r$ of edge-disjoint trees $T_1,T_2,\cdots ,T_r$ in $G$ such that $V(T_i)\bigcap V(T_j)=S$ for any $i,j\in \{1,2,\cdots ,r\}$ and $i\ne j$. For an integer $k$ with $2\le k\le n$, the {\em generalized $k$-connectivity} of a graph $G$ is defined as ${\kappa }_k(G)=min\{{\kappa }_G(S)|S\subseteq V(G)$ and $|S|=k\}$. In this paper, we study the generalized $3$-connectivity of some general $m$-regular and $m$-connected graphs $G_n$ constructed recursively and obtain that ${\kappa }_3(G_n)=m-1$, which attains the upper bound of ${\kappa }_3(G)$ [Discrete Mathematics 310 (2010) 2147-2163] given by Li {\em et al.} for $G=G_n$. As applications of the main result, the generalized $3$-connectivity of many famous networks such as the alternating group graph $A{G}_n$, the $k$-ary $n$-cube $Q_n^k$, the split-star network $S_n^2$ and the bubble-sort-star graph $B{S}_n$ etc. can be obtained directly.

19 pages, 6 figures