The strong giant in a random digraph

DOI10.1017/JPR.2015.8MaRDI QIDQ2804412zbMATHOpenAlexFDO

Authors Mathew D. Penrose

Publication date 29 April 2016

Published in Journal of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

branching processgiant componentsemi-homogeneous random digraph

Mathematics Subject Classification ID

Epidemiology (92D30) Random graphs (graph-theoretic aspects) (05C80) Applications of branching processes (60J85)

Abstract: Consider a random directed graph on $n$ vertices with independent identically distributed outdegrees with distribution $F$ having mean $mu$, and destinations of arcs selected uniformly at random. We show that if $mu>1$ then for large $n$ there is very likely to be a unique giant strong component with proportionate size given as the product of two branching process survival probabilities, one with offspring distribution $F$ and the other with Poisson offspring distribution with mean $mu$. If $muleq1$ there is very likely to be no giant strong component. We also extend this to allow for $F$ varying with $n$.

Recommendations

• Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs
• On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
• On the largest strong components in \(m\)-out digraphs
• Giant components in three-parameter random directed graphs
• Birth of a strongly connected giant in an inhomogeneous random digraph

Cites work

• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• Birth of a strongly connected giant in an inhomogeneous random digraph
• Information Transmission under Random Emission Constraints
• On the connectivity of random m-orientable graphs and digraphs
• Random graphs.
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence

Cited in

(14)

• Birth of a strongly connected giant in an inhomogeneous random digraph
• Typical distances in the directed configuration model
• Giant components in three-parameter random directed graphs
• Directed cycles and related structures in random graphs. I: Static properties
• Connectivity of a general class of inhomogeneous random digraphs
• The giant component of the directed configuration model revisited
• The scaling limit of a critical random directed graph
• Locality of random digraphs on expanders
• Birth of a giant \((k_{1},k_{2})\)-core in the random digraph
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs
• The diameter of the directed configuration model
• On the largest strong components in \(m\)-out digraphs
• The birth of the strong components

This page was built for publication: The strong giant in a random digraph

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