THE MAXIMUM AND MINIMUM DEGREES OF RANDOM BIPARTITE MULTIGRAPHS

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

Abstract

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; {p_k}) the probability space consisting of all the labeled bipartite multigraphs with two vertex sets A = {a₁, a₂, · · · , a_n} and B ={b₁, b₂, · · · , b_m}, 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{t_ai,_bj= k} = p_k, k = 0, 1, 2, · · · ,
where p_k ≥ 0 and ∑^∞ _k=0 p_k = 1. They obtain that Xc,d,A, the number of vertices in A with degree between c and d of G_n,m ∈G(n, m; {p_k}) has asymptotically Poisson distribution, and answer the following two questions about the space 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 ∈ 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 ∈ G(n, m; {p_k}) a unique vertex of maximum degree in A?

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

CLC Number:

05C80

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.

Trendmd

References

[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)