✳flâneur — a map of the web's best reading

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

arxiv.org · 64 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? Let $k\ge 2$ be fixed integer, $0&lt;c&lt;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.

Explore this link on the map →

saved by

related reading