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
| CREATOR | Juan Gutierrez, Kaustav Paul |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.29199