Distributions of sparse spanning subgraphs in random graphs

2011/05/30 by Pu Gao, Gao, Pu
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1105.5913

17 pages, 2 figures

arxiv created 2015/01/15 · arxiv updated 2015/01/16

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.

Related

• Induced subgraphs in sparse random graphs with given degree sequence
• On the probability that a random subtree is spanning
• Random perturbation of sparse graphs
• Random cliques in random graphs revisited
• Subgraph distributions in dense random regular graphs