The strong giant in a random digraph

DOI10.1017/JPR.2015.8zbMATH Open1335.05164arXiv1409.4371OpenAlexW1838920763MaRDI QIDQ2804412FDOQ2804412

Authors: Mathew D. Penrose 

Publication date: 29 April 2016

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

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$.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Random graphs.
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• Birth of a strongly connected giant in an inhomogeneous random digraph
• On the connectivity of random m-orientable graphs and digraphs
• Information Transmission under Random Emission Constraints

Cited In (9)

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

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)