Extremal Graphs with Local Covering Conditions
Authors:
- Debsoumya ChakrabortiDCDebsoumya Chakraborti
- Po-Shen LohPLPo-Shen Loh
- 1 January 2020
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 34 (2) , 1354-1374
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 Erdös--Rényi 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.
Keywords
All Related Versions
Funding Information
- National Science Foundation (DMS-1455125)
This publication has 10 references indexed in Scilit:
- The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum DegreeJournal of Graph Theory, 2016
- Introduction to Random Graphs2015
- Maximizing the Number of Independent Sets of a Fixed SizeCombinatorics, Probability and Computing, 2014
- Counting Independent Sets of a Fixed Size in Graphs with a Given Minimum DegreeJournal of Graph Theory, 2013
- Random Graphs2001
- What we know and what we do not know about Turán numbersGraphs and Combinatorics, 1995
- Degree sequences of random graphsDiscrete Mathematics, 1981
- A Problem in Graph TheoryThe American Mathematical Monthly, 1964
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963
- On the structure of linear graphsBulletin of the American Mathematical Society, 1946