RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 1995 Volume 7, Issue 4, Pages 86–94 (Mi dm609)

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.

UDC: 519.2

Received: 15.11.1994


 English version:
Discrete Mathematics and Applications, 1995, 5:6, 515–523

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024