The Generalized Connectivity of Complete Equipartition 3-Partite Graphs

Shasha Li ; Wei Li ; Xueliang Li

Bulletin of the Malaysian Mathematical Society, Tome 37 (2014) no. 1

Résumé

Let $G$ be a nontrivial connected graph of order $n$, and $k$ an integer with $2\leq k\leq n$. For a set $S$ of $k$ vertices of $G$, let $\kappa (S)$ denote the maximum number $\ell$ of edge-disjoint trees $T_1,T_2,\ldots,T_\ell$ in $G$ such that $V(T_i)\cap V(T_j)=S$ for every pair of distinct integers $i,j$ with $1\leq i,j\leq \ell$.Chartrand \emph{et al.} generalized the concept of connectivity as follows: The $k$-$connectivity$ of $G$, denoted by $\kappa_k(G)$, is defined by $\kappa_k(G)=$min$\{\kappa(S)\}$, where the minimum is taken overall $k$-subsets $S$ of $V(G)$. Thus $\kappa_2(G)=\kappa(G)$, where $\kappa(G)$ is the connectivity of $G$; whereas, $\kappa_{n}(G)$ is the maximum number of edge-disjoint spanning trees contained in $G$. This paper mainly focuses on the $k$-connectivity of complete equipartition 3-partite graphs $K^{3}_{b}$, where $b\geq 2$ is an integer. First, we obtain the number of edge-disjoint spanning trees of a general complete 3-partite graph $K_{x,y,z}$, which is $\lfloor(xy+yz+zx)/(x+y+z-1)\rfloor$. Then, based on this result, we get the $k$-connectivity of $K^{3}_{b}$ for all $3\leq k \leq 3b$.

Détail

Classification : 05C40, 05C05