Name
Title | ||
|---|---|---|
Maximum Sparse Induced Subgraphs Of The Binomial Random Graph With Given Number Of Edges |
Abstract | ||
|---|---|---|
We prove that a.a.s. the maximum size of an induced subtree of the binomial random graph G(n, p) is concentrated in 2 consecutive points. We also prove that, given a non negative integer-valued function t(k) < epsilon k(2), under a certain smoothness condition on this function, a.a.s. the maximum size k of an induced subgraph with exactly t(k) edges of G(n, p) is concentrated in 2 consecutive points as well. (c) 2020 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.disc.2020.112205 | DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
Random graph, Maximum induced subgraphs, Maximum induced tree | Journal | 344 |
Issue | ISSN | Citations |
2 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kamaldinov Dmitry | 1 | 0 | 0.34 |
| Skorkin Arkadiy | 2 | 0 | 0.34 |
| Maksim Zhukovskii | 3 | 2 | 4.51 |