Name
Abstract | ||
|---|---|---|
We systematically study a natural problem in extremal graph theory, to minimize the number of edges in a graph with a fixed number of vertices, subject to a certain local condition: each vertex must be in a copy of a fixed graph H. We completely solve this problem when H is a clique, as well as more generally when H is any regular graph with degree at least about half its number of vertices. We also characterize the extremal graphs when H is an Erdos-Renyi random graph. The extremal structures turn out to have the similar form as the conjectured extremal structures for a well-studied but elusive problem of similar flavor with local constraints: to maximize the number of copies of a fixed clique in graphs in which all degrees have a fixed upper bound. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1137/19M1286712 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
extremal graph theory,local covering,random graphs | Journal | 34 |
Issue | ISSN | Citations |
2 | 0895-4801 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chakraborti Debsoumya | 1 | 0 | 0.34 |
| Po-Shen Loh | 2 | 133 | 18.68 |