Paper Info
Title
On dominating sets whose induced subgraphs have a bounded diameter
Abstract
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=1 it is NP-complete to decide whether a given graph admits a dominating set whose induced subgraph has diameter at most k. 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 X can be chosen such that any shortest path between two members of the dominating set is entirely contained in X. Moreover, the characterization yields an O(mn) algorithm to compute, for a given connected chordal graph G on n vertices and m edges, the minimum k for which G has a dominating set whose induced subgraph has diameter at most k. Such a dominating set can be efficiently computed.
Year
DOI
Venue
2013
10.1016/j.dam.2013.05.030
Discrete Applied Mathematics
Keywords
Field
DocType
induced subgraph,dominating set x,bounded diameter,minimum k,induced subgraphs,dominating set,m edge,chordal graph,characterization yield,fixed k,sensor networks
Discrete mathematics,Combinatorics,Dominating set,Chordal graph,Induced subgraph,Distance-hereditary graph,Connected dominating set,Mathematics,Domatic number,Bidimensionality,Maximal independent set
Journal
Volume
Issue
ISSN
161
16-17
0166-218X
Citations 
PageRank 
References 
2
0.37
12
Authors
1
Name
Order
Citations
PageRank
Oliver Schaudt19521.74