“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 16338  


Abstract:  
A dominating set is a set S of vertices in a graph such that every vertex not in S is adjacent to a vertex in S. In this paper, we consider the set of all optimal (i.e. smallest) dominating sets S, and ask of the existence of at least one such set S with given constraints. The constraints say that the number of neighbors in S of a vertex inside S must be in a given set Ï, and the number of neighbors of a vertex outside S must be in a given set ï¿½?. For example, if Ï is , and ï¿½? is the nonnegative integers, this corresponds to ï¿½??
domination.ï¿½?ï¿½
First, we consider the complexity of recognizing whether an optimal dominating set with given constraints exists or not. We show via two different reductions that this problem is NPhard for certain given constraints. This, in particular, answers a question of [M. Chellali et al.,
dominating sets in graphs, Discrete Applied Mathematics 161 (2013) 2885ï¿½??2893] regarding the constraint that the number of neighbors in the set be upperbounded by 2. We also consider the corresponding question regarding ï¿½??totalï¿½?ï¿½ dominating sets.
Next, we consider some wellstructured classes of graphs, including permutation and interval graphs (and their subfamilies), and determine exactly the smallest k such that for all graphs in that family an optimal dominating set exists where every vertex is dominated at most k times. We also consider the problem for trees (with implications for chordal and comparability graphs) and graphs with bounded ï¿½??asteroidal numberï¿½?ï¿½.
Download TeX format 

back to top 