Acta mathematica scientia, Series B >
THE MAXIMUM AND MINIMUM DEGREES OF RANDOM BIPARTITE MULTIGRAPHS
Received date: 2008-06-29
Revised date: 2010-03-05
Online published: 2011-05-20
Supported by
The work was supported by NSFC (10671162; 10831001; 10871046).
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?
CHEN Ai-Lian , ZHANG Fu-Ji , LI Hao . THE MAXIMUM AND MINIMUM DEGREES OF RANDOM BIPARTITE MULTIGRAPHS[J]. Acta mathematica scientia, Series B, 2011 , 31(3) : 1155 -1166 . DOI: 10.1016/S0252-9602(11)60306-8
[1] Bollob´as B, Klee V. Diameters of random bipartite graphs. Combinatorica, 1984, 4(1): 7–19
[2] Klee V E, Larman D G, Wright E M. The diameter of almost all bipartite graphs. Studia Sci Math Hung, 1980, 15: 39–43
[3] Alon N, Krivelevich M. The choice number of random bipartite graphs. Ann Combin, 1998, 2: 291–297
[4] Frieze A. Limit distribution for the existence of hamiltonian cycles in random bipartite graphs. Europ J Combin, 1985, 6: 327–334
[5] Erd¨os P. Graph theory and probability. Canad J Math, 1959, 11: 34–38
[6] Ivchenko G I. On the asymptotic behavior of the degrees of vertices in a random graph. Theory Probab Appl, 1973, 18: 188–195
[7] Erd¨os P, Wilson R J. On the chromatic index of almost all graphs. J Combin Theory B, 1977, 23: 255–257
[8] Bollob´as B. The distribution of the maximum degree of a random graph. Discrete Math, 1980, 32: 201–203
[9] Bollob´as B. Degree sequences of random graphs. Discrete Math, 1981, 33: 1–19
[10] Bollob´as B. Vertices of given degree in a random graph. J Graph Theory, 1982, 6: 147–155
[11] Jordan J. The degree sequences and spectra of scale-free random graphs. Random Struct Alg, 2006, 29: 226–242
[12] Szyma´nski J. Concentration of vertex degrees in a scale-Free random graph process. Random Struct Alg, 2005, 26: 224–236
[13] Cooper C. Distribution of vertex degree in web-graphs. Combin Probab Comput, 2006, 15(5): 637–661
[14] Berger N, Bollob´as B, Borgs C, Chayes J, Riordanetal O. Degree distribution of the FKP network model. Theoretical Computer Science, 2007, 379(3): 306–316
[15] He W C, Feng L, Li L Y, Xu C Q. Time evolution of the degree distribution of model A of random attachment growing networks. Phys A: Stat Mech Appl, 2007, 384: 663–666
[16] Bollob´as B, Mckay B D. The number of matchings in random regular graphs and bipartite graphs. J Combin Theory B, 1986, 41(1): 80–91
[17] Walkup D W. Matchings in random regular bipartite digraphs. Discrete Math, 1980, 31: 59–64
[18] Kiwi M, Loebl M. Largest planar matching in random bipartite graphs. Random Struct Alg, 2002, 21(2): 162–181
[19] Kalugin I B. The number of component of a random bipartite graph. Discrete Math Appl, 1991, 1(3): 289–299
[20] Frieze A. Perfect matchings in random bipartite graphs with minimal degree at least 2. Random Struct Alg, 2005, 26(3): 319–358
[21] Saltykov A I. The number of components in a random bipartite graph. Discrete Math Appl, 1995, 5(6): 515–523
[22] Mckay B D, Wormald N C. Uniform generation of random regular graphs of moderate degree. J Alg, 1990, 11(1): 52–67
[23] Bollob´as B. Counting coloured graphs of high connectivity. Canad J Math, 1981, 33: 476–484
[24] Klee V L, Larman D G, Wright E M. The proportion of labelled bipartite graphs which are connected. J London Math Soc, 1981, 24: 397–404
[25] Erd¨os P, R´enyi A. On random matrices. Publ Math Inst Hung Acad Sci, 1963, 8(A): 455–461
[26] Erd¨os P, R´enyi A. On the existence of a factor of degree one of a connected random graph. Acta Math Acad Sci Hungar, 1966, 17: 359–368
[27] Frieze A, Pittel B. Perfect matchings in random graphs with prescribed minimal degree//Proceedings of SODA. 2003: 148–159
[28] Bollob´as B. Random Graphs. 2nd ed. London: Cambridge University Press, 2001
[29] Feller W. An Introduction to Probability Theory and its Applications. Vols II. New York: John Wiley and Sons, 1966
[30] Erd¨os P, Rubin A L, Taylor H. Choosability in graphs//Proc West Coast Conf (Combin, Graph Theory and Computing, Congressus Numerantium), 1979, 26: 125–157
[31] Chen A, Zhang F, Li H. The degree distribution of random multigraphs. Acta Mathematica Sinica, English Series, 2011, 27(12) (Accepted)
/
| 〈 |
|
〉 |