THE MAXIMUM AND MINIMUM DEGREES OF RANDOM BIPARTITE MULTIGRAPHS

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

数学物理学报(英文版) ›› 2011, Vol. 31 ›› Issue (3): 1155-1166.doi: 10.1016/S0252-9602(11)60306-8

THE MAXIMUM AND MINIMUM DEGREES OF RANDOM BIPARTITE MULTIGRAPHS

陈爱莲|张福基|李皓

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

收稿日期:2008-06-29 修回日期:2010-03-05 出版日期:2011-05-20 发布日期:2011-05-20
基金资助:
The work was supported by NSFC (10671162; 10831001; 10871046).

THE MAXIMUM AND MINIMUM DEGREES OF RANDOM BIPARTITE MULTIGRAPHS

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

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; {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?

关键词: maximum degree, minimum degree, degree distribution, random bipartite multigraphs

Abstract:

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

中图分类号:

05C80

陈爱莲, 张福基, 李皓. THE MAXIMUM AND MINIMUM DEGREES OF RANDOM BIPARTITE MULTIGRAPHS[J]. 数学物理学报(英文版), 2011, 31(3): 1155-1166.

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.

参考文献

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

THE MAXIMUM AND MINIMUM DEGREES OF RANDOM BIPARTITE MULTIGRAPHS

THE MAXIMUM AND MINIMUM DEGREES OF RANDOM BIPARTITE MULTIGRAPHS

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

Metrics

本文评价

推荐阅读 10