Limiting shape of the depth first search tree in an Erdős‐Rényi graph
Nathanaël Enriquez, Gabriel Faraud, Laurent Ménard · Random Structures and Algorithms · 2019
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 with c > 1 converges to an explicit deterministic shape. This makes it possible to exhibit a long nonintersecting path of length , where ρc is the density of the giant component and Li2 denotes the dilogarithm function.