Limiting shape of the depth first search tree in an Erdős-Rényi graph

DOI10.1002/RSA.20878MaRDI QIDQ5113947zbMATH OpenOpenAlexFDO

Authors Nathanaël Enriquez, Gabriel Faraud, L. Ménard

Publication date 19 June 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.00696

zbMATH Keywords

depth first search algorithmErdős-Rényi graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: We show that the profile of the tree constructed by the Depth First Search Algorithm in the giant component of an ErdH{o}s-R'enyi 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(h{o}_c-fracmathrm{Li}_2(h{o}_c)cight)imesN$, where $h{o}_c$ is the density of the giant component.

Recommendations

• Depth first exploration of a configuration model
• On the performance of the depth first search algorithm in supercritical random graphs
• On depth first search trees in \(m\)-out digraphs
• A local limit theorem for the critical random graph
• On the fluctuations of the giant component

Cited in

(6)

• Respondent-driven sampling on sparse Erdös-Rényi graphs
• On the performance of the depth first search algorithm in supercritical random graphs
• Chain-referral sampling on stochastic block models
• Depth first exploration of a configuration model
• On depth first search trees in \(m\)-out digraphs
• Depth-first search performance in a random digraph with geometric outdegree distribution

This page was built for publication: Limiting shape of the depth first search tree in an Erdős-Rényi graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113947)