Largest sparse subgraphs of random graphs.
For the Erdos-Rényi random graph Gn,p, we consider the order of a largest vertex subset that induces a subgraph with average degree at most t. For the case when both p and t are fixed, this value is asymptotically almost surely concentrated on at most two explicitly given points. This generalises a...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Jezik: | English |
| Izdano: |
2011
|