On dominating sets whose induced subgraphs have a bounded diameter

We study dominating sets whose induced subgraphs have a bounded diameter. Such sets were used in recent papers by Kim et al. and Yu et al. to model virtual backbones in wireless networks where the number of hops required to forward messages within the backbone is minimized.We prove that for any fixed k≥1k≥1 it is NP-complete to decide whether a given graph admits a dominating set whose induced subgraph has diameter at most kk.On the upside, we give a characterization of the chordal graphs that admit such a dominating set. It turns out that in this characterization, the dominating set XX can be chosen such that any shortest path between two members of the dominating set is entirely contained in XX. Moreover, the characterization yields an O(mn)O(mn) algorithm to compute, for a given connected chordal graph GG on nn vertices and mm edges, the minimum kk for which GG has a dominating set whose induced subgraph has diameter at most kk. Such a dominating set can be efficiently computed.