Generalized 3-edge-connectivity of Cartesian product graphs

Sun, Yuefang

Czechoslovak Mathematical Journal, Tome 65 (2015) no. 1, pp. 107-117.

Résumé

The generalized $k$-connectivity $\kappa _{k}(G)$ of a graph $G$ was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized $k$-edge-connectivity which is defined as $\lambda _k(G) = \min \{\lambda (S)\colon S \subseteq V(G)$ and $|S|= k\}$, where $\lambda (S)$ denotes the maximum number $\ell $ of pairwise edge-disjoint trees $T_1, T_2, \ldots , T_{\ell }$ in $G$ such that $S\subseteq V(T_i)$ for $1\leq i\leq \ell $. In this paper we prove that for any two connected graphs $G$ and $H$ we have $\lambda _3(G\square H)\geq \lambda _3(G)+\lambda _3(H)$, where $G\square H$ is the Cartesian product of $G$ and $H$. Moreover, the bound is sharp. We also obtain the precise values for the generalized 3-edge-connectivity of the Cartesian product of some special graph classes.

Détail

DOI : 10.1007/s10587-015-0162-9

Classification : 05C40, 05C76
Keywords: generalized connectivity; generalized edge-connectivity; Cartesian product