Links

Tools

Export citation

Search in Google Scholar

The generalized 3-connectivity of random graphs

Journal article published in 2013 by Ran Gu, Xueliang L. Li, Yongtang T. Shi ORCID
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Question mark in circle
Preprint: policy unknown
Question mark in circle
Postprint: policy unknown
Question mark in circle
Published version: policy unknown

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 $κ(S)$ be defined as the largest number of internally disjoint trees $T_1, T_2, ⋯, T_k$ connecting $S$ in $G$. Then for an integer $r$ with $2 ≤ r ≤ n$, the {\it generalized $r$-connectivity} $κ_r(G)$ of $G$ is the minimum $κ(S)$ where $S$ runs over all the $r$-subsets of the vertex set of $G$. Obviously, $κ_2(G)=κ(G)$, is the vertex connectivity of $G$, and hence the generalized connectivity is a natural generalization of the vertex connectivity. Similarly, let $λ(S)$ denote the largest number $k$ of pairwise edge-disjoint trees $T_1, T_2, …, T_k$ connecting $S$ in $G$. Then the {\it generalized $r$-edge-connectivity} $λ_r(G)$ of $G$ is defined as the minimum $λ(S)$ where $S$ runs over all the $r$-subsets of the vertex set of $G$. Obviously, $λ_2(G) = λ(G)$. In this paper, we study the generalized 3-connectivity of random graphs and prove that for every fixed integer $k≥ 1$, $p=\frac{{\log n+(k+1)\log \log n -\log \log \log n}}{n}$ is a sharp threshold function for the property $κ_3(G(n, p)) ≥ k$, which could be seen as a counterpart of Bollobás and Thomason's result for vertex connectivity. Moreover, we obtain that $δ (G(n,p)) - 1 = λ (G(n,p)) - 1 = κ (G(n,p)) - 1 \le {κ_3}(G(n,p)) \le {λ_3}(G(n,p)) \le κ (G(n,p)) = λ (G(n,p)) = δ (G(n,p))$ almost surely holds, which could be seen as a counterpart of Ivchenko's result. ; Comment: 14 pages