Domination-packing ratio for planar and unit disk graphs

Abstract

The domination number ${\hat{I}}^3(G)$ of a graph $G$ is the smallest possible size of a vertex set that intersects every radius-$1$ ball of $G$, and the packing number $\ddot{I}(G)$ is the maximum number of pairwise vertex-disjoint radius-$1$ balls. We prove that $\frac{{\hat{I}}^3(G)}{\ddot{I}(G)}\le 5$ for every planar graph and $\frac{{\hat{I}}^3(G)}{\ddot{I}(G)}\le \frac{18\sqrt{3}}{\ddot{I}}€\approx 9.924$ for every unit disk graph, thus yielding Erdős-Pósa-type bounds for the hypergraph of radius-$1$ balls in the two graph classes. This improves upon results of Gutiérrez and Paul, and Dúcz and Gujgiczer, who in turn lowered bounds of Bonamy, Csikós, Gujgiczer and Yuditsky, and Böhme and Mohar. For both graph classes, the best known lower bound on the optimal constant remains $3$.

9 pages

Topics & keywords