Vertices of given degree in a random graph
Author:
- 1 June 1982
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 6 (2) , 147-155
Abstract
This paper concerns the degree sequence d1 ≥ d2 ≥ … ≥ dn of a randomly labeled graph of order n in which the probability of an edge is p(n) ≦ 1/2. Among other results the following questions are answered. What are the values of p(n) for which d1, the maximum degree, is the same for almost every graph? For what values of p(n) is it true that d2 > d2 for almost every graph, that is, there is a unique vertex of maximum degree? The answers are (essentially) p(n) = o(logn/n/n) and p(n)n/logn → ∞. Also included is a detailed study of the distribution of degrees when 0 < lim n p(n)/log n ≦ lim n p(n)/log n < ∞.Keywords
This publication has 3 references indexed in Scilit:
- Degree sequences of random graphsDiscrete Mathematics, 1981
- On the chromatic index of almost all graphsJournal of Combinatorial Theory, Series B, 1977
- Advanced Combinatorics1974