کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4664629 1345302 2011 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The maximum and minimum degrees of random bipartite multigraphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات (عمومی)
پیش نمایش صفحه اول مقاله
The maximum and minimum degrees of random bipartite multigraphs
چکیده انگلیسی

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 GG(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,bjtai,bj of the edges between any two vertices ai ∈ A and bj ∈ B are identically distributed independent random variables with distributionP{tai,bj = k} = pk, k = 0, 1, 2, ⋯,P{tai,bj = k} = pk, k = 0, 1, 2, ⋯,where pk ≥ 0 and ∑pk = 1k=0∞. They obtain that Xc,d,A, the number of vertices in A with degree between c and d of Gn, m ∈ GG (n, m;{pk}) has asymptotically Poisson distribution, and answer the following two questions about the space GG(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 ∈ GG (n, m;{pk}) has maximum degree D(n) in A? under which condition for {pk} has almost every multigraph Gn, m ∈ GG (n, m;{pk}) a unique vertex of maximum degree in A?

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Acta Mathematica Scientia - Volume 31, Issue 3, May 2011, Pages 1155–1166
نویسندگان
, , ,