On the k-hop domination numbers of spanning trees of unicyclic graphs

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 khop 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.