首页 | 本学科首页   官方微博 | 高级检索  
     


The maximum and minimum degrees of random bipartite multigraphs
Authors:Ailian Chen
Affiliation:a College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China
b School of Mathematical Sciences, Xiamen University, Xiamen 361005, China
c Laboratoire de Recherche en Informatique, UMR 8623, C. N. R. S. -Université de Paris-sud, 91405-Orsay cedex, France
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 ζ(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∈A and bj∈ 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∈ζ(n, m;{pk}) has asymptotically Poisson distribution, and answer the following two questions about the space ζ(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∈ζ(n,m;{pk}) has maximum degree D(n)in A? under which condition for {pk} has almost every multigraph G(n,m)∈ζ(n,m;{pk}) a unique vertex of maximum degree in A?
Keywords:maximum degree   minimum degree   degree distribution   random bipartite multigraphs
本文献已被 CNKI 维普 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号