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 ∈ N, a subset Dhd of the vertex set V is a d-hop connected dominating set of the graph G if each vertex t ∈ V is situated at most d-steps from at least one vertex z ∈ Dhd, that is, d(t, z) ≤ d, and the subgraph of G induced by Dhd is connected. If Dhd 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 Dhd 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.