{"id":"arxiv/2604.27639","url":"https://arxiv.org/abs/2604.27639","tags":["math.CO"],"score":0,"title":"How large part of a graph can be covered by the neighborhoods of k vertices?","domain":"math.CO","source":"arxiv","authors":["Janos Pach"],"reviews":0,"subject":"math.CO","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-30","reactions":{}}