What Fraction of the Vertex Set of a Graph can be Covered by $k$ Neighborhoods?
Let $k\ge 2$ be a fixed integer, $0<c<1$ a constant. Consider a graph $G$ with $n$ vertices and average degree $cn$. We answer a question of Simon Griffiths by showing that $G$ has $k$ vertices such that their neighborhoods together cover at least $\min\bigl(1-(1-c)^{k},\sqrt{c}\,\bigr)n$ vertices. This result is essentially tight.
Authors
- János Pach (ORCID: https://orcid.org/0000-0002-2389-2035)
Publication Details
- Journal
- The Electronic Journal of Combinatorics
- Published
- 2026-11-20
- DOI
- https://doi.org/10.37236/15672
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Academia Sinica
- Nemzeti Kutatási Fejlesztési és Innovációs Hivatal