Tight upper bounds on the hop domination number of triangle-free graphs
Shinya Fujita · 2025
Read Tight upper bounds on the hop domination number of triangle-free graphs by Shinya Fujita (2025) 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-2503-04124.txt.
Description
Shinya Fujita and Boram Park set tight limits on a graph measure in a 2025 math study. A hop dominating set is a set of points such that every point outside it sits exactly two steps from a point inside. The hop domination number is the size of the smallest such set. The team studies connected graphs with no triangles and at least fifteen points, where each point has at least two neighbors.
For such graphs they prove the number is at most two fifths of the point count, and the bound cannot be improved. They also give tight bounds for graphs that hold a path or a cycle through all points. The results pin down how sparse a two-step watch set can be.
Catalog record
| CREATOR | Shinya Fujita |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-04124