The generalized 3-connectivity of random graphs

Abstract

The generalized connectivity of a graph $G$ was introduced by Chartrand et al. Let $S$ be a nonempty set of vertices of $G$, and $\kappa (S)$ be defined as the largest number of internally disjoint trees $T_1,T_2,\cdots ,T_k$ connecting $S$ in $G$. Then for an integer $r$ with $2\le r\le n$, the {\it generalized $r$-connectivity} ${\kappa }_r(G)$ of $G$ is the minimum $\kappa (S)$ where $S$ runs over all the $r$-subsets of the vertex set of $G$. Obviously, ${\kappa }_2(G)=\kappa (G)$, is the vertex connectivity of $G$, and hence the generalized connectivity is a natural generalization of the vertex connectivity. Similarly, let $\lambda (S)$ denote the largest number $k$ of pairwise edge-disjoint trees $T_1,T_2,\dots ,T_k$ connecting $S$ in $G$. Then the {\it generalized $r$-edge-connectivity} ${\lambda }_r(G)$ of $G$ is defined as the minimum $\lambda (S)$ where $S$ runs over all the $r$-subsets of the vertex set of $G$. Obviously, ${\lambda }_2(G)=\lambda (G)$. In this paper, we study the generalized 3-connectivity of random graphs and prove that for every fixed integer $k\ge 1$, $$p=\frac{\log n+(k+1)\log \log n-\log \log \log n}{n}$$ is a sharp threshold function for the property ${\kappa }_3(G(n,p))\ge k$, which could be seen as a counterpart of Bollobás and Thomason's result for vertex connectivity. Moreover, we obtain that $\delta (G(n,p))-1=\lambda (G(n,p))-1=\kappa (G(n,p))-1\le {\kappa }_3(G(n,p))\le {\lambda }_3(G(n,p))\le \kappa (G(n,p))=\lambda (G(n,p))=\delta (G(n,p))$ almost surely holds, which could be seen as a counterpart of Ivchenko's result.

14 pages

References in corpus (2)

• On extremal graphs with at most two internally disjoint Steiner trees connecting any three vertices
• The generalized 3-connectivity of Cartesian product graphs