The generalized 3-connectivity of Cartesian product graphs

Abstract

The generalized connectivity of a graph, which was introduced recently by Chartrand et al., is a generalization of the concept of vertex connectivity. Let $S$ be a nonempty set of vertices of $G$, a collection $\{T_1,T_2,...,T_r\}$ of trees in $G$ is said to be internally disjoint trees connecting $S$ if $E(T_i)\cap E(T_j)=\varnothing$ and $V(T_i)\cap V(T_j)=S$ for any pair of distinct integers $i,j$, where $1\le i,j\le r$. For an integer $k$ with $2\le k\le n$, the $k$-connectivity ${\kappa }_k(G)$ of $G$ is the greatest positive integer $r$ for which $G$ contains at least $r$ internally disjoint trees connecting $S$ for any set $S$ of $k$ vertices of $G$. Obviously, ${\kappa }_2(G)=\kappa (G)$ is the connectivity of $G$. Sabidussi showed that $\kappa (G\square H)\ge \kappa (G)+\kappa (H)$ for any two connected graphs $G$ and $H$. In this paper, we first study the 3-connectivity of the Cartesian product of a graph $G$ and a tree $T$, and show that $(i)$ if ${\kappa }_3(G)=\kappa (G)\ge 1$, then ${\kappa }_3(G\square T)\ge {\kappa }_3(G)$; $(ii)$ if $1\le {\kappa }_3(G)<\kappa (G)$, then ${\kappa }_3(G\square T)\ge {\kappa }_3(G)+1$. Furthermore, for any two connected graphs $G$ and $H$ with ${\kappa }_3(G)\ge {\kappa }_3(H)$, if $\kappa (G)>{\kappa }_3(G)$, then ${\kappa }_3(G\square H)\ge {\kappa }_3(G)+{\kappa }_3(H)$; if $\kappa (G)={\kappa }_3(G)$, then ${\kappa }_3(G\square H)\ge {\kappa }_3(G)+{\kappa }_3(H)-1$. Our result could be seen as a generalization of Sabidussi's result. Moreover, all the bounds are sharp.

17 pages

References in corpus (2)

• The generalized connectivity of complete bipartite graphs
• Hardness results on generalized connectivity