Universality of random graphs for graphs of maximum degree two

Abstract

For a family $\mathcal{F}$ of graphs, a graph $G$ is called \emph{$\mathcal{F}$-universal} if $G$ contains every graph in $\mathcal{F}$ as a subgraph. Let ${\mathcal{F}}_n(d)$ be the family of all graphs on $n$ vertices with maximum degree at most $d$. Dellamonica, Kohayakawa, Rödl and Ruciński showed that, for $d\ge 3$, the random graph $G(n,p)$ is ${\mathcal{F}}_n(d)$-universal with high probability provided $p\ge C(\frac{\log n}{n}{)}^{1/d}$ for a sufficiently large constant $C=C(d)$. In this paper we prove the missing part of the result, that is, the random graph $G(n,p)$ is ${\mathcal{F}}_n(2)$-universal with high probability provided $p\ge C(\frac{\log n}{n}{)}^{1/2}$ for a sufficiently large constant $C$.

13 pages, 1 figure

Cited by in corpus (1)

• Universality of random graphs and rainbow embedding