Extremal Graphs with Local Covering Conditions

Authors:
  • DCDebsoumya Chakraborti
    Debsoumya Chakraborti
  • PLPo-Shen Loh
    Po-Shen Loh

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.
Funding Information
  • National Science Foundation (DMS-1455125)

This publication has 10 references indexed in Scilit: