Equivalence dominating sets in graphs (Q2860824)

An equivalence set is a subset of vertices of a graph \(G\) with the property that every component of the subgraph induced by it is complete. In this paper, the authors define equivalence dominating and equivalence irredundant sets (equivalence sets that are dominating and irredundant, respectively) as well as several parameters associated to these concepts: the equivalence number and lower equivalence number are the maximum and minimum cardinality of a maximal (with respect to inclusion) equivalence set, the equivalence domination number and upper equivalence domination number are the minimum and maximum cardinality of a minimal equivalence dominating set, and the equivalence irredundance number and upper equivalence irredundance number are the minimum and maximum cardinality of a maximal equivalence irredundant set.NEWLINENEWLINEThese parameters are related to their classical counterparts (independence number, domination number, etc.) and to each other by various inequalities. Moreover, the authors show that the decision problems relating to the equivalence domination number and upper equivalence domination number are NP-complete.