The first cycles in an evolving graph

DOI10.1016/0012-365X(89)90087-3zbMath0696.05045OpenAlexW1966433910MaRDI QIDQ910415

Donald E. Knuth, Philippe Flajolet, Boris G. Pittel

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)90087-3

zbMATH Keywords

generating functionsrandom graph processgraph evolution

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Exact enumeration problems, generating functions (05A15) Paths and cycles (05C38)

Related Items (38)

Parking functions for mappings ⋮ Forbidden subgraphs in connected graphs ⋮ On the number of circuits in random graphs ⋮ Cycles in a random graph near the critical point ⋮ Cycles in a Uniform Graph Process ⋮ Perfect hashing ⋮ Threshold functions for small subgraphs in simple graphs and multigraphs ⋮ Multicyclic components in a random graph process ⋮ The birth of the strong components ⋮ Random 2 XORSAT phase transition ⋮ On the threshold for \(k\)-regular subgraphs of random graphs ⋮ Parking on Cayley trees and frozen Erdős-Rényi ⋮ Branch structure and implementation of Lambert \(W\) ⋮ Cores of random \(r\)-partite hypergraphs ⋮ First cycles in random directed graph processes ⋮ The cook-book approach to the differential equation method ⋮ Infinitary logics and very sparse random graphs ⋮ When does the top homology of a random simplicial complex vanish? ⋮ D?E?K=(1000)8 ⋮ Random maps, coalescing saddles, singularity analysis, and Airy phenomena ⋮ Phase transition of random non-uniform hypergraphs ⋮ Counting connected graphs with large excess ⋮ Cycles of given lengths in unicyclic components in sparse random graphs ⋮ Non-principal Branches of Lambert W. A Tale of 2 Circles ⋮ 2-Xor revisited: satisfiability and probabilities of functions ⋮ The Diagonal Poisson Transform and its application to the analysis of a hashing scheme ⋮ A critical point for random graphs with a given degree sequence ⋮ Random 2-XORSAT at the Satisfiability Threshold ⋮ Expected Maximum Block Size in Critical Random Graphs ⋮ Multiscale dynamics of an adaptive catalytic network ⋮ Large cycles in random generalized Johnson graphs ⋮ On the probability of planarity of a random graph near the critical point ⋮ A double large prime variation for small genus hyperelliptic index calculus ⋮ The Bohman-Frieze process near criticality ⋮ The maximal length of 2-path in random critical graphs ⋮ Unnamed Item ⋮ Analytic description of the phase transition of inhomogeneous multigraphs ⋮ On the chromatic number of a random hypergraph

Cites Work

• Poisson convergence and Poisson processes with applications to random graphs
• The expected linearity of a simple equivalence algorithm
• A Random Graph With a Subcritical Number of Edges
• The number of connected sparsely edged graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The first cycles in an evolving graph