A linear time algorithm for optimal k-hop dominating set of a tree

We give a linear time algorithm to compute an optimal (minimum) k‐hop dominating set D of a tree T for $k⩾1$ . This extends the previous result for an optimal 1‐dominating set for trees. We use a rooted form $\overline{T}$ of T, with an arbitrary node selected as the root, to direct the search for nodes of D in a bottom–up fashion. The decision whether to include a node x in D or not is based on the subtree of $\overline{T}$ at x. Optimal k‐hop dominating sets have many important practical applications.