Distance paired-domination problems on subclasses of chordal graphs

Abstract: Let be a graph without isolated vertices. For a positive integer , a set is a -distance paired-dominating set if each vertex in is within distance of a vertex in and the subgraph induced by contains a perfect matching. In this paper, we present two linear time algorithms to find a minimum cardinality -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 -distance paired-dominating set. [Copyright &y& Elsevier]