Skip to main content
Improved title
Link

Trees and unicyclic The structure of small components in random graphs with a given degree sequence

Source Link

Trees and unicyclic components in random graphs with a given degree sequence

Background and definitions

Consider a random graph on $n$ vertices with a nicely behaved degree sequence. That is, letting $d_i(n)$ denote the number of vertices of degree $i$, suppose that for all $i$, there exists a constant $\lambda_i$ such that $d_i(n)/n \to \lambda_i$ as $n \to \infty$.

Let $G$ be a randomly chosen graph with this degree sequence. Molloy and Reed proved that as $n \to \infty$, if $\sum_{i = 0}^{\infty} i(i - 2)\lambda_i > 0$, then w.h.p. $G$ has a giant component, while if $\sum_{i = 0}^{\infty} i(i - 2)\lambda_i < 0$, then w.h.p. $G$ does not have a giant component.

Moreover, the same authors gave a formula for the limiting size of the giant component in the former case.

My question concerns the "small" components in the case where a giant component exists. In the case of an Erdos-Renyi random graph $G_{n,p}$, the structure of these components is well understood: if $p = cn/2$ for some $c > 1$, then with high probability the graph is the union of the giant component, small tree components, and a growing but relatively small number of unicyclic components. (For a precise statement of this, see Theorem 6.11 of Bollobas's Random Graphs.)

My question

For which degree sequences is it true that with high probability the small components are mostly trees with a comparatively small number of unicyclic components? In some cases, it's easy to see that no small component can be a tree: for example, in the case of an $r$-regular graph for $r \geq 2$, $G$ cannot contain a tree, because every tree has a vertex of degree $1$. (However, for $r \geq 3$, the results in the second paper linked to above show that w.h.p. the giant component consists of the entire graph, so in this case the desired property holds vacuously.) So, for which degree sequences is it "non-trivially" true that most small components are trees?

(N.B.: In the first paper linked to above, Molloy and Reed showed that in the "subcritical" case in which there is no giant component, w.h.p. every component contains at most one cycle.)

The motivation

I'm teaching a course on complex networks using M.E.J. Newman's Networks: An Introduction. In the chapter on random graphs with a given degree sequence (see SEction 13.7), the author claims that for essentially any given degree sequence, almost all of the small components are trees. However, the argument given is far from rigorous, and I am rather skeptical of the conclusion.