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.

Received: 4 September 2020 | Accepted: 7 May 2022