Extremal Graphs with Local Covering Conditions

DOI10.1137/19M1286712zbMATH Open1444.05072arXiv1909.04873MaRDI QIDQ3300760

Author name not available (Why is that?)

Publication date: 30 July 2020

Published in: (Search for Journal in Brave)

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 ErdH{o}s-R'enyi 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.

Full work available at URL: https://arxiv.org/abs/1909.04873

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Extremal Graphs with Local Covering Conditions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3300760)