In this section we want to present some results on the random graph model of Erdőos and Rényi [19, 20]. This model is defined as follows. Given are *n* vertices with labels 1,..., *n* and a probability *p*. Then each possible edge is included in the edge set of the graph with probability *p*, where all edges are treated independently. The resulting graph is denoted by *G*(*n*, *p*). A second model is considering the set of all graphs with *n* vertices and *m* edges and choosing one graph uniformly at random. This graph is called *G*(*n*, *m*) and it is known that the two models are equivalent in many respects, provided that *p* is close to *m* (see [28, Section 1.4] for details).

One interesting phenomenon of random graphs is the emergence of a giant component. If we let *n* → ∞ and set *p* = *c*/*n*, thenfor *c* < 1 a typical graph consists of small and simple components, that is, each component has a typical size of *O*(log *n*) and does not contain many cycles. If *c* > 1, then a typical graph consists of one giant component that comprises roughly two thirds of all vertices and many small and simple components. The phase transition occurring around *c* = 1 was thoroughly studied by Janson *et al*. [27].

When analyzing the phase transition at the emergence of a giant component, it is of prime importance to understand the behavior ...

Start Free Trial

No credit card required