×

Extreme degrees in random graphs. (English) Zbl 0672.05069

Starting from a fixed labelled graph on n vertices, its edges are independently kept or removed with probability p and 1-p, resp. The degree sequence of the resulting random graph is investigated by using factorial moment properties of the degree distribution as n tends to infinity. The general approach is applied to random subgraphs of a complete bipartite graph.
Reviewer: O.Frank

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C35 Extremal problems in graph theory
60F05 Central limit and other weak theorems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bollobás, Discrete Math. 32 pp 201– (1980) · Zbl 0441.05031 · doi:10.1016/0012-365X(80)90054-0
[2] Bollobás, Discrete Math. 33 pp 1– (1981)
[3] Bollobás, Canadian J. Math. 33 pp 476– (1981) · Zbl 0484.05042 · doi:10.4153/CJM-1981-041-2
[4] Bollobás, J. Graph Theory 6 pp 147– (1982)
[5] Degree sequences of random graphs (to appear).
[6] Erdös, Publ. Math. Inst. Hung. Acad. Sci. 5 pp 17– (1960)
[7] Erdös, Acta Math. Acad. Sci. Hung. 12 pp 261– (1961)
[8] Erdös, J. Comb. Th. Ser. B 23 pp 255– (1977)
[9] An Introduction to Probability Theory and its Applications, Vol. 1. Wiley, New York (1968).
[10] Ivchenko, Theory Prob. Appl. 18 pp 188– (1973)
[11] Karoński, J. Graph Theory 6 pp 349– (1982)
[12] Klee, J. London Math. Soc. (2) 24 pp 397– (1981)
[13] Palka, J. Graph Theory 8 pp 167– (1984)
[14] Palka, Periodica Math. Hung. 15 pp 121– (1984)
[15] Palka, Math. Proc. Cambridge Phil. Soc. 97 pp 69– (1985)
[16] Palka, Math. Proc. Cambridge Phil. Soc. 100 pp 167– (1986)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.