On graph classes with constant domination-packing ratio
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913724590194688 |
|---|---|
| author | Bonamy, Marthe Csikós, Mónika Gujgiczer, Anna Yuditsky, Yelena |
| author_facet | Bonamy, Marthe Csikós, Mónika Gujgiczer, Anna Yuditsky, Yelena |
| contents | The dominating number $γ(G)$ of a graph $G$ is the minimum size of a vertex set whose closed neighborhood covers all the vertices of the graph. The packing number $ρ(G)$ of $G$ is the maximum size of a vertex set whose closed neighborhoods are pairwise disjoint. In this paper we study graph classes ${\cal G}$ such that $γ(G)/ρ(G)$ is bounded by a constant $c_{\cal G}$ for each $G\in {\cal G}$. We propose an inductive proof technique to prove that if $\cal G$ is the class of $2$-degenerate graphs, then there is such a constant bound $c_{\cal G}$. We note that this is the first monotone, dense graph class that is shown to have constant ratio. We also show that the classes of AT-free and unit-disk graphs have bounded ratio.
In addition, our technique gives improved bounds on $c_{\cal G}$ for planar graphs, graphs of bounded treewidth or bounded twin-width. Finally, we provide some new examples of graph classes where the ratio is unbounded. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_05562 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On graph classes with constant domination-packing ratio Bonamy, Marthe Csikós, Mónika Gujgiczer, Anna Yuditsky, Yelena Combinatorics Discrete Mathematics The dominating number $γ(G)$ of a graph $G$ is the minimum size of a vertex set whose closed neighborhood covers all the vertices of the graph. The packing number $ρ(G)$ of $G$ is the maximum size of a vertex set whose closed neighborhoods are pairwise disjoint. In this paper we study graph classes ${\cal G}$ such that $γ(G)/ρ(G)$ is bounded by a constant $c_{\cal G}$ for each $G\in {\cal G}$. We propose an inductive proof technique to prove that if $\cal G$ is the class of $2$-degenerate graphs, then there is such a constant bound $c_{\cal G}$. We note that this is the first monotone, dense graph class that is shown to have constant ratio. We also show that the classes of AT-free and unit-disk graphs have bounded ratio. In addition, our technique gives improved bounds on $c_{\cal G}$ for planar graphs, graphs of bounded treewidth or bounded twin-width. Finally, we provide some new examples of graph classes where the ratio is unbounded. |
| title | On graph classes with constant domination-packing ratio |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2503.05562 |