Limiting shape of the depth first search tree in an Erdős‐Rényi graph. Issue 2 (18th July 2019)

• Record Type: Journal Article
• Authors: Enriquez, Nathanaël; Faraud, Gabriel; Ménard, Laurent
• Is Part Of: Random structures & algorithms. Volume 56:Issue 2(2020)
• Page Start: 501
• Page End: 516
• Publication Date: 2019-07-18
• Subjects: depth first search algorithm -- Erdős‐Rényi graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20878
• Languages: English
• ISSNs: 1042-9832

Abstract

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.