Domination-packing ratio for planar and unit disk graphs

Abstract

The domination number $γ(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 $ρ(G)$ is the maximum number of pairwise vertex-disjoint radius-$1$ balls. We prove that $\frac{γ(G)}{ρ(G)}\le 5$ for every planar graph and $\frac{γ(G)}{ρ(G)} \le \frac{18\sqrt3}π\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$.

Disclosure

“livray and Seyffarth [MS96, Theorem 1]. For its extension to arbitrary X, the separation and connector arguments of [GH02], particularly Lemma 13, appear relevant but in need of multiple pages of proof. The latter approach was suggested by ChatGPT 5.6 Sol in the final phase of this project, when we uploaded this draft and asked it to find this specific improvement. Since we prefer to keep the note short and easy to follow, we do not pursue that technical extension here. Upon asking”

PDF page 7

Classification

Drafting limited passages

Multiplier

5

Verified

2026-08-23T18:55:26.965982Z

Structural counts