Combinatorics Probability Computing · 1992 · 98 citations · 2 references
EngineeringGraph TheoryRandom GraphExtremal Graph TheoryDegree RestrictionsMaximum DegreeStructural Graph TheoryProbabilistic Graph TheoryInduced GraphN Isolated VerticesExtremal CombinatoricsProbability TheoryCombinatorial Optimization
Suppose that a process begins with n isolated vertices, to which edges are added randomly one by one so that the maximum degree of the induced graph is always bounded above by d . We prove that if n → ∞ with d fixed, then with probability tending to 1, the final result of this process is a graph with ⌊ nd / 2⌋ edges.
2