Limiting shape of the Depth First Search tree in an Erdős-Rényi graph

Abstract

We show that the profile of the tree constructed by the Depth First Search Algorithm in the giant component of an Erdős-Rényi graph with $N$ vertices and connection probability $c/N$ converges to an explicit deterministic shape. This makes it possible to exhibit a long non-intersecting path of length $\left({\rho }_c-\frac{{\mathrm{Li}}_2({\rho }_c)}{c}\right)\times N$, where ${\rho }_c$ is the density of the giant component.

16 pages, 3 figures