r-Dominating cliques in graphs with hypertree structure Original Research Article

et G = (V, E) be an undirected graph and r be a vertex weight function with positive integer values. A subset (clique) D ⊆ V is an r-dominating set (clique) in G iff for every vertex v ϵ V there is a vertex u ϵ D with dist (u, v) ⩽ r(v). This paper contains the following results: 1. (i) We give a simple necessary and sufficient condition for the existence of r-dominating cliques in the case of Helly graphs and of chordal graphs. 2. (ii) For Helly graphs with an r-dominating clique the minimum size of an r-dominating clique coincides with the minimum size of any r-dominating set. 3. (iii) We give a linear-time algorithm for finding a minimum r-dominating clique in dually chordal graphs (a generalization of strongly chordal graphs). These results improve and extend earlier results on r-dominating cliques in chordal and strongly chordal graphs.