On graph classes with constant domination-packing ratio

Abstract

The dominating number ${\hat{I}}^3(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 $\ddot{I}(G)$ of $G$ is the maximum size of a vertex set whose closed neighborhoods are pairwise disjoint. In this paper we study graph classes $\mathcal{G}$ such that ${\hat{I}}^3(G)/\ddot{I}(G)$ is bounded by a constant $c_{\mathcal{G}}$ for each $G\in \mathcal{G}$. We propose an inductive proof technique to prove that if $\mathcal{G}$ is the class of $2$-degenerate graphs, then there is such a constant bound $c_{\mathcal{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_{\mathcal{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.