06002341

j

06002341 Chen, Ailian Zhang, Fuji Li, Hao The maximum and minimum degrees of random bipartite multigraphs. Acta Math. Sci., Ser. B, Engl. Ed. 31, No. 3, 1155-1166 (2011). 2011 Science Press, Beijing EN maximum degree minimum degree degree distribution random bipartite multigraphs

doi:10.1016/S0252-9602(11)60306-8

Summary: In this paper, the authors generalize the classic random bipartite graph model, and define a model of the random bipartite multigraphs as follows: let $m=m (n)$ be a positive integer-valued function on $n$ and ${\cal G} (n, m; \{p_k\})$ the probability space consisting of all the labeled bipartite multigraphs with two vertex sets $A=\{a_1, a_2,\cdots, a_n\}$ and $B=\{b_1, b_2,\cdots, b_m\}$, in which the numbers $t_{a_i,b_j}$ of the edges between any two vertices $a_i\in A$ and $b_j\in B$ are identically distributed independent random variables with distribution $$P\{t_{a_i,b_j}=k\}=p_k,\quad k=0,1,2,\cdots,$$ where $p_k\geq 0$ and $\sum\limits^\infty_{k=0}p_k=1$. They obtain that $X_{c,d,A}$, the number of vertices in $A$ with degree between $c$ and $d$, of $G_{n,m}\in {\cal G} (n,m;\{p_k\})$ has asymptotically Poisson distribution, and answer the following two questions about the space ${\cal G} (n,m;\{p_k\})$ with $\{p_k\}$ having geometric distribution, binomial distribution and Poisson distribution, respectively. Under which condition for $\{p_k\}$ can there be a function $D (n)$ such that almost every random multigraph $G_{n,m}\in {\cal G} (n,m;\{p_k\})$ has maximum degree $D (n)$ in $A$? Under which condition for $\{p_k\}$ has almost every multigraph $G_{n,m}\in {\cal G} (n,m;\{p_k\})$ a unique vertex of maximum degree in $A$?