On Subgraph Sizes in Random Graphs
- 1 June 1992
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 1 (2) , 123-134
Abstract
For a graph G with m edges let its Range of Subgraph Sizes (RSS)ρ(G) = {t : G contains a vertex-induced subgraph with t edges}.G has a full RSS if ρ(G) = {0, 1, …, m}. We establish the threshold for a random graph to have a full RSS and give tight bounds on the likely RSS of a dense random graph.Keywords
This publication has 1 reference indexed in Scilit:
- Stable husbandsRandom Structures & Algorithms, 1990