On the k-Hop Domination Numbers of Spanning Trees of Unicyclic Graphs

Wattana Jindaluang, Nopadon Juneam

Abstract

The work of Kundu and Majumder (Kundu and Majumder, 2016) leads to an approach to determine the $k$-hop domination number of a connected graph by examining the $k$-hop domination numbers of its spanning trees. Given this approach, a quadratic-time algorithm to compute the $k$-hop domination number of a unicyclic graph can be derived. In this article, we prove that the $k$-hop domination numbers of a unicyclic graph and its spanning trees differ by at most one, thus yielding a linear-time algorithm for finding a near-optimal $k$-hop dominating set with the tightly bounded error of $1$.