“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 16338
School of Mathematics
Title:   When an optimal dominating set with given constraints exists
Author(s):
 1 Omid Etesami 2 Narges Ghareghani 3 Pouyeh Sharifani (Joint with M. Habib, M.R. Hooshmandasl, and R. Naserasr)
Status:   Published
Journal: Theoretical Computer Science
Vol.:  780
Year:  2019
Pages:   54-65
Supported by:  IPM
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 NP-hard 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 upper-bounded by 2. We also consider the corresponding question regarding ï¿½??totalï¿½?ï¿½ dominating sets.
Next, we consider some well-structured 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ï¿½?ï¿½.