First cycles in random directed graph processes

DOI10.1016/0012-365X(89)90078-2MaRDI QIDQ910414zbMATH OpenFDO

Authors Béla Bollobás, Steen Rasmussen

Publication date 1989

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(89)90078-2

zbMATH Keywords

cyclesgraph evolutionrandom graph processes

Mathematics Subject Classification ID

Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80) Martingales with discrete parameter (60G42)

Review text

A directed graph process is defined by successively letting each one of n vertices send out k edges with equal probabilities given to the \(\left( \begin{matrix} n\\ k\end{matrix} \right)\) choices. At time t, exactly t of the vertices have sent out their edges. Martingale theory is used to prove some results about the distribution of the length of the first cycle.

Recommendations

• The first cycles in an evolving graph
• Getting a directed Hamilton cycle two times faster
• Directed cycles and related structures in random graphs. I: Static properties
• Counting Hamilton cycles in sparse random directed graphs
• Long paths and cycles in dynamical graphs

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3566657 (Why is no real title available?)
• scientific article; zbMATH DE number 4128851 (Why is no real title available?)
• scientific article; zbMATH DE number 3390276 (Why is no real title available?)
• On generalized graphs
• Poisson convergence and Poisson processes with applications to random graphs
• The equilibrium statistics of a clustering process in the uncondensed phase
• The first cycles in an evolving graph
• Weighted sums of certain dependent random variables

Cited in

(8)

• The emergence of a self-catalysing structure in abstract origin-of-life models
• Directed cycles and related structures in random graphs. I: Static properties
• Minimal autocatalytic networks
• Cycles in a Uniform Graph Process
• Multiscale dynamics of an adaptive catalytic network
• Contagion-based safety premium in bank networks
• Random biochemical networks: the probability of self-sustaining autocatalysis
• The first cycles in an evolving graph

This page was built for publication: First cycles in random directed graph processes

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