Improved Domination--Packing Bounds in Claw-Free Cubic Graphs and Unit Disk Graphs

Abstract

Given a graph $G$, the domination number ${\hat{I}}^3(G)$ is the minimum cardinality of a dominating set in $G$, and the packing number $\ddot{I}(G)$ is the maximum cardinality of a set of vertices that are pairwise at distance at least $3$. The ratio between these parameters has been widely studied in several graph classes. It is known that ${\hat{I}}^3(G)\le 2\ddot{I}(G)$ for claw-free subcubic graphs, up to finitely many exceptions, and that ${\hat{I}}^3(G)\le 32\ddot{I}(G)$ for unit disk graphs. In this paper, we improve the latter bound by showing that ${\hat{I}}^3(G)\le 16\ddot{I}(G)$ for a unit disk graph $G$. For the former bound, we show that it can be improved in the cubic bridgeless setting; more precisely, every bridgeless claw-free cubic graph $G$ satisfies ${\hat{I}}^3(G)\le \frac{7}{4}\ddot{I}(G)+\frac{5}{6}$. These results are not tight. In fact, we give example of an infinite family of bridgeless cubic graphs $G$ with ${\hat{I}}^3(G)=5\ddot{I}(G)/4$ and an infnite family of unit disk graphs $G$ in which ${\hat{I}}^3(G)=3\ddot{I}(G)$.