Induced subgraphs in sparse random graphs with given degree sequence

2010/11/16 by Pu Gao, Yi Su, Gao, Pu +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1011.3810

openalex publication_date 2010/11/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For any S⊂ [n], we compute the probability that the subgraph of G_n,d induced by S is a given graph H on the vertex set S. The result holds for any d=o(n^1/3) and is further extended to G_{\bf d}, the probability space of random graphs with a given degree sequence \bf d.

Related

• Trees in Random Sparse Graphs with a Given Degree Sequence
• Subgraphs of dense random graphs with specified degrees
• Large induced subgraphs of random graphs with given degree sequences
• Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity
• Subgraphs in random graphs with specified degrees and forbidden edges