Paper detail

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

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( ρ_c - \frac{\mathrm{Li}_2(ρ_c)}{c} \right) \times N$, where $ρ_c$ is the density of the giant component.