The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph

DOI10.1017/S0963548300001012zbMath0809.05084WikidataQ105583879 ScholiaQ105583879MaRDI QIDQ4306436

Svante Janson

Publication date: 20 March 1995

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

decompositionenumerationHamiltonian cyclesmatchingsrandom graphpermanentspanning trees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Determinants, permanents, traces, other special matrix functions (15A15) Enumeration in graph theory (05C30) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eulerian and Hamiltonian graphs (05C45)

Related Items (31)

Limit theorems for random permanents with exchangeable structure ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ The number of Hamiltonian decompositions of regular graphs ⋮ Perfect matchings and derangements on graphs ⋮ On the probability that a random subtree is spanning ⋮ The number of perfect matchings, and the nesting properties, of random regular graphs ⋮ Subgraph distributions in dense random regular graphs ⋮ A transition of limiting distributions of large matchings in random graphs ⋮ Triangles and subgraph probabilities in random regular graphs ⋮ Determinant-Preserving Sparsification of SDDM Matrices ⋮ Random Regular Graphs: Asymptotic Distributions and Contiguity ⋮ Law of the iterated logarithm for random graphs ⋮ Unions of random trees and applications ⋮ Regular induced subgraphs of a random Graph ⋮ Packing, counting and covering Hamilton cycles in random directed graphs ⋮ Powers of Hamilton cycles in pseudorandom graphs ⋮ The number of possibilities for random dating ⋮ The matching energy of a graph ⋮ Approximation theorems for random permanents and associated stochastic processes ⋮ Hamilton cycles in a random tournament ⋮ On the permanent of random Bernoulli matrices ⋮ Limiting behavior of random permanents ⋮ Random directed graphs are robustly Hamiltonian ⋮ On the permanent of a random symmetric matrix ⋮ Incomplete U -statistics of permanent design ⋮ Hamiltonian cycles above expectation in \(r\)-graphs and quasi-random \(r\)-graphs ⋮ The set of ratios of derangements to permutations in digraphs is dense in \([0,1/2\)] ⋮ Edge Correlations in Random Regular Hypergraphs and Applications to Subgraph Testing ⋮ On the expected number of perfect matchings in cubic planar graphs ⋮ An analysis of Monte Carlo algorithm for estimating the permanent ⋮ Distribution of the number of spanning regular subgraphs in random graphs

Cites Work

• When are small subgraphs of a random graph normally distributed?
• Random trees in a graph and trees in a random graph
• Counting the Number of Hamilton Cycles in Random Digraphs

This page was built for publication: The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph