How large part of a graph can be covered by the neighborhoods of k vertices?
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913076368900096 |
|---|---|
| author | Pach, Janos |
| author_facet | Pach, Janos |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_27639 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | How large part of a graph can be covered by the neighborhoods of k vertices? Pach, Janos Combinatorics 05C35, 05C69 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. |
| title | How large part of a graph can be covered by the neighborhoods of k vertices? |
| topic | Combinatorics 05C35, 05C69 |
| url | https://arxiv.org/abs/2604.27639 |