Domination and packing in graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914399271256064 |
|---|---|
| author | Dúcz, Ákos Gujgiczer, Anna |
| author_facet | Dúcz, Ákos Gujgiczer, Anna |
| contents | The dominating number $γ(G)$ of a graph $G$ is the minimum size of a vertex set whose closed neighborhoods cover all vertices of $G$, while the packing number $ρ(G)$ is the maximum size of a vertex set whose closed neighborhoods are pairwise disjoint. In this paper we investigate graph classes $\mathcal{G}$ for which the ratio $γ(G)/ρ(G)$ is bounded by a constant $c_{\mathcal{G}}$ for every $G \in \mathcal{G}$. Our main result is an improved upper bound on this ratio for planar graphs. We also extend the list of graph classes admitting a bounded ratio by showing this for chordal bipartite graphs and for homogeneously orderable graphs. In addition, we provide a simple, direct proof for trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_18402 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Domination and packing in graphs Dúcz, Ákos Gujgiczer, Anna Combinatorics 05C69, 05C70 The dominating number $γ(G)$ of a graph $G$ is the minimum size of a vertex set whose closed neighborhoods cover all vertices of $G$, while the packing number $ρ(G)$ is the maximum size of a vertex set whose closed neighborhoods are pairwise disjoint. In this paper we investigate graph classes $\mathcal{G}$ for which the ratio $γ(G)/ρ(G)$ is bounded by a constant $c_{\mathcal{G}}$ for every $G \in \mathcal{G}$. Our main result is an improved upper bound on this ratio for planar graphs. We also extend the list of graph classes admitting a bounded ratio by showing this for chordal bipartite graphs and for homogeneously orderable graphs. In addition, we provide a simple, direct proof for trees. |
| title | Domination and packing in graphs |
| topic | Combinatorics 05C69, 05C70 |
| url | https://arxiv.org/abs/2602.18402 |