Improved Domination--Packing Bounds in Claw-Free Cubic Graphs and Unit Disk Graphs
Given a graph $G$, the domination number $γ(G)$ is the minimum cardinality of a dominating set in $G$, and the packing number $ρ(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 $γ(G) \le 2ρ(G)$ for claw-free subcubic graphs, up to finitely many exceptions, and that $γ(G) \le 32ρ(G)$ for unit disk graphs. In this paper, we improve the latter bound by showing that $γ(G) \le 16ρ(G)$ for a unit disk graph $G$. For the former bound, we show that it…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.29199
curl -X POST /api/v1/records/arxiv/2606.29199/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.29199/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'