Computation of minimum d-hop connected dominating set of trees in O(n) time

Abstract

For a graph G=(V,E) and a fixed constant $d\in \mathbb{N}$, a subset D_{hd} of the vertex set V is a d-hop connected dominating set of the graph G if each vertex $t\in V$ is situated at most d-steps from at least one vertex $z\in D_{hd}$, that is, $d(t,z)\leq d$, and the subgraph of G induced by $D_{hd}$ is connected. If $D_{hd}$ has minimum cardinality, then it is a minimum d-hop connected dominating set. In this paper, we present two O(n)-time algorithms for computing a minimum $D_{hd}$ of trees with n vertices. We also design an algorithm to find the central vertices of a tree. Besides that, we also study some properties related to hop-domination on trees.