|
Abstract
|
The study of random graphs emerged as a distinct field with the influential
paper by Erd¨os and R´enyi, and it is widely regarded as one of the most important areas
within graph theory. Different models of random graphs exist, each characterized by its
unique probability distribution for generating graphs. One approach involves starting
with individual vertices and randomly adding edges between them. Various random
graph models generate distinct probability distributions for the resulting graphs. One of
the frequently studied models is denoted as G(n, p), encompassing all labeled graphs with
n vertices. In this model, each possible edge appears independently with a probability
of 0 ⩽ p ⩽ 1. Another natural model of random graphs is denoted as G(n, m), which
represents the probability space of all labeled graphs with n vertices and exactly m edges.
|