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