Distance paired-domination problems on subclasses of chordal graphs

Let G=(V,E) be a graph without isolated vertices. For a positive integer k, a set S⊆V is a k-distance paired-dominating set if each vertex in V−S is within distance k of a vertex in S and the subgraph induced by S contains a perfect matching. In this paper, we present two linear time algorithms to find a minimum cardinality k-distance paired-dominating set in interval graphs and block graphs, which are two subclasses of chordal graphs. In addition, we present a characterization of trees with unique minimum k-distance paired-dominating set.