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

arxiv.org · 2,285 words · saved by 1 readers

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.

How large part of a graph can be covered by the neighborhoods of k vertices? János Pach∗ arXiv:2604.27639v1 [math.CO] 30 Apr 2026 Abstract Let k ≥ 2 be fixed integer, 0 < c < 1 a constant. Consider a graph G with n vertices and…

saved by

Luke Hawranick

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

saved by

related reading