Distributions of Sparse Spanning Subgraphs in Random Graphs

DOI10.1137/120866300zbMATH Open1268.05178arXiv1105.5913OpenAlexW2068735212MaRDI QIDQ5300501FDOQ5300501

Pu Gao

Publication date: 27 June 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We describe a general approach of determining the distribution of spanning subgraphs in the random graph $G(n,p)$. In particular, we determine the distribution of spanning subgraphs of certain given degree sequences, which is a generalisation of the $d$-factors, of spanning triangle-free subgraphs, of (directed) Hamilton cycles and of spanning subgraphs that are isomorphic to a collection of vertex disjoint (directed) triangles.

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

zbMATH Keywords

asymptotic distributionHamilton cycleswitchingspanning subgraphstriangle-factorstriangle-free subgraphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Eulerian and Hamiltonian graphs (05C45)

Cited In (10)

• On local weak limit and subgraph counts for sparse random graphs
• Empirical spectral distributions of sparse random graphs
• Law of the iterated logarithm for random graphs
• Random Subgraphs in Sparse Graphs
• A transition of limiting distributions of large matchings in random graphs
• Spanning subgraphs of random graphs
• Bivariate fluctuations for the number of arithmetic progressions in random sets
• Triangles and subgraph probabilities in random regular graphs
• The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph
• Distribution of coefficients of rank polynomials for random sparse graphs

This page was built for publication: Distributions of Sparse Spanning Subgraphs in Random Graphs

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