Acta mathematica scientia,Series B ›› 2011, Vol. 31 ›› Issue (3): 1155-1166.doi: 10.1016/S0252-9602(11)60306-8

• Articles • Previous Articles     Next Articles

THE MAXIMUM AND MINIMUM DEGREES OF RANDOM BIPARTITE MULTIGRAPHS

 CHEN Ai-Lian, ZHANG Fu-Ji, LI Hao   

  1. College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China; School of Mathematical Sciences, Xiamen University, Xiamen 361005, China; Laboratoire de Recherche en Informatique, UMR 8623, C. N. R. S. -Universit´e de Paris-sud, 91405-Orsay cedex, France
  • Received:2008-06-29 Revised:2010-03-05 Online:2011-05-20 Published:2011-05-20
  • Supported by:

    The work was supported by NSFC (10671162; 10831001; 10871046).

Abstract:

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 G(n, m; {pk}) the probability space consisting of all the labeled bipartite multigraphs with two vertex sets A = {a1, a2, · · · , an} and B ={b1, b2, · · · , bm}, in which the numbers tai,bj of the edges between any two vertices ai 2 A and bj 2 B are identically distributed independent random variables with distribution

P{tai,bj = k} = pk, k = 0, 1, 2, · · · ,
where pk ≥ 0 and ∑ k=0 pk = 1. They obtain that Xc,d,A, the number of vertices in A with degree between c and d of Gn,m ∈G(n, m; {pk}) has asymptotically Poisson distribution, and answer the following two questions about the space G(n, m; {pk}) with {pk} having geometric distribution, binomial distribution and Poisson distribution, respectively. Under which condition for {pk} can there be a function D(n) such that almost every random multigraph Gn,m ∈ G(n, m; {pk}) has maximum degree D(n) in A? under which condition for {pk} has almost every multigraph Gn,m ∈ G(n, m; {pk}) a unique vertex of maximum degree in A?

Key words: maximum degree, minimum degree, degree distribution, random bipartite multigraphs

CLC Number: 

  • 05C80
Trendmd