A note on r-dominating cliques Original Research Article

Let M be a finite subset of vertices of a connected graph G and assume that every vertex v ∈ M has a dominating radius r(v) ∈ N ∪ [0]. A complete subgraph C is an r-dominating clique of M if every vertex v ∈ M is at distance at most r(v) from C. Even for r(v)  1 the problem whether or not a given graph has an r-dominating clique is NP-complete. Evidently, if M admits an r-dominating clique then d(u,v) ⩽ r(u) + r(v) + 1 for any u, v ∈ M. We characterize the graphs G for which this condition guarantees the existence of r-dominating cliques not only in G but also in all isometric subgraphs of G comprising M. These are the graphs which do not contain the house, the 3-deltoid, or any n-cycle with n ⩾ 5 as an isometric subgraph.