How large part of a graph can be covered by the neighborhoods of k vertices?

Abstract

Let $k\ge 2$ be 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 (1-(1-c{)}^k,\sqrt{c})n$ vertices. This result is essentially tight.

6 pages, 0 figure