What Fraction of the Vertex Set of a Graph can be Covered by $k$ Neighborhoods?

  • János Pach

Abstract

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.

Published
2026-11-20
How to Cite
Pach, J. (2026). What Fraction of the Vertex Set of a Graph can be Covered by $k$ Neighborhoods?. The Electronic Journal of Combinatorics, 33(4), #P4.42. https://doi.org/10.37236/15672
Article Number
P4.42