|
The number of components in a random bipartite graph
A. I. Saltykov
Abstract:
We consider a bipartite graph $G(n_1,n_2,T)$ with $n_1$ vertices in the first part and
$n_2$ vertices in the second one. This graph is obtained by $T$ independent trials, each of
them consists of drawing an edge which joins two vertices chosen independently of each
other from distinct parts. Let
$n_1\ge n_2$, $\alpha=n_2/n_1$, $n=n_1+n_2$. We prove that if $n\to\infty$
and $(1+\alpha)T=n\ln n+xn+o(n)$, where $x$ is a fixed number, then, with probability
tending to one, the graph $G(n_1,n_2,T)$ contains one giant connected component and
isolated vertices whose number is distributed by the Poisson law.
Received: 15.11.1994
Citation:
A. I. Saltykov, “The number of components in a random bipartite graph”, Diskr. Mat., 7:4 (1995), 86–94; Discrete Math. Appl., 5:6 (1995), 515–523
Linking options:
https://www.mathnet.ru/eng/dm609 https://www.mathnet.ru/eng/dm/v7/i4/p86
|
| Statistics & downloads: |
| Abstract page: | 486 | | Full-text PDF : | 221 | | References: | 2 | | First page: | 2 |
|