DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 16(2) (1996) 157-172
DOI: 10.7151/dmgt.1031

POISSON CONVERGENCE OF NUMBERS OF VERTICES OF A GIVEN DEGREE IN RANDOM GRAPHS

Wojciech Kordecki

Institute of Mathematics, Technical University of Wrocław
Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

e-mail: kordecki@im.pwr.wroc.pl

Abstract

The asymptotic distributions of the number of vertices of a given degree in random graphs, where the probabilities of edges may not be the same, are given. Using the method of Poisson convergence, distributions in a general and particular cases (complete, almost regular and bipartite graphs) are obtained.

Keywords: Random graphs, degrees of vertices, Poisson convergence.

1991 Mathematics Subject Classification: Primary 05C80, Secondary 60C05.

References

[1] A.D. Barbour, Poisson convergence and random graphs, Math. Proc. Camb. Phil. Soc. 92 (1982) 349-359, doi: 10.1017/S0305004100059995.
[2] A.D. Barbour and G.K. Eagleason, Poisson approximation for some statistics based on exchangeable trials, Adv. Appl. Prob. 15 (1983) 585-600, doi: 10.2307/1426620.
[3] A.D. Barbour, L. Holst and S. Janson, Poisson approximation (Clarendon Press, Oxford, 1992).
[4] M. Karoński and A. Ruciński, Poisson convergence and semiinduced properties of random graphs, Math. Proc. Camb. Phil. Soc. 101 (1987) 291-300, doi: 10.1017/S0305004100066664.
[5] V.L. Klee, D.G. Larman and E.M. Wright, The proportion of labelled bipartite graphs which are connected, J. London Math. Soc. 24 (1981) 397-404, doi: 10.1112/jlms/s2-24.3.397.
[6] W. Kordecki, Vertices of given degree in a random graph, Prob. Math. Stat. 11 (1991) 287-290.
[7] Z. Palka, On the degrees of vertices in a bichromatic random graph, Period. Math. Hung. 15 (1984) 121-126, doi: 10.1007/BF01850725.
[8] Z. Palka, Asymptotic properties of random graphs, Dissertationes Mathematicae, CCLXXV (PWN, Warszawa, 1998).
[9] Z. Palka and A. Ruciński, Vertex-degrees in a random subgraph of a regular graph, Studia Scienc. Math. Hung. 25 (1990) 209-214.