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

CREATORShinya Fujita
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-04124

Browse the full library · About the Tower of Babel