×

Almost every bipartite graph has not two vertices of minimum degree. (English) Zbl 0795.05126

The difference between the minimum degrees of the two parts of the random bipartite graph \(K_{m,n,p}\) is estimated, and it is shown that a vertex of minimum degree is a. s. unique for \(m\) and \(n\) growing nearly equally. A similar result is proved for maximum degrees.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: EuDML

References:

[1] BOLLOBÁS B.: Degree sequences of random graphs. Discrete Math. 33 (1981), 1-19. · Zbl 0447.05038 · doi:10.1016/0012-365X(81)90253-3
[2] BOLLOBÁS B.: Vertices of given degree in a random graph. J. Graph Theory 6 (1982), 147-155. · Zbl 0499.05056 · doi:10.1002/jgt.3190060209
[3] ERDÖS P., WILSON R. J.: On the chromatic index of almost all graphs. J. Combin. Theory Ser. B 23 (1977), 255-257. · Zbl 0378.05032 · doi:10.1016/0095-8956(77)90039-9
[4] FELLER W.: An Introduction to Probability Theory and its Applications Vol 1. Wiley, New York, 1968. · Zbl 0155.23101
[5] PALKA Z.: Extreme degrees in random graphs. J. Graph Theory 11 (1987), 121-134. · Zbl 0672.05069 · doi:10.1002/jgt.3190110202
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.