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

Juan Gutierrez, Kaustav Paul · 2026

Read Improved Domination–Packing Bounds in Claw-Free Cubic Graphs and Unit Disk Graphs by Juan Gutierrez, Kaustav Paul (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-29199.txt.

Description

Gutierrez and Paul improve bounds linking two graph quantities. Domination is the smallest set of vertices that watches over the whole graph. Packing is the largest set of vertices pairwise far apart. Their ratio has been studied across many graph classes. For unit disk graphs, where vertices are points and edges join nearby points, the domination number was known to be at most thirty-two times the packing number.

The authors halve that bound to sixteen times. For claw-free cubic graphs, graphs where every vertex has three neighbours and no claw shape appears, the known bound was twice the packing number apart from finitely many exceptions. In the bridgeless cubic case they improve it to seven quarters of the packing number plus a small constant. Neither result is tight. Infinite families reach five quarters in the cubic case and three in the unit disk case.

Catalog record

CREATORJuan Gutierrez, Kaustav Paul
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.29199

Browse the full library · About the Tower of Babel