Majority domination in graphs (Q1842153)

The majority number of a graph is a new numerical invariant of a graph concerning domination; it is defined by means of the majority dominating function. A majority dominating function is a function \(f:V \to \{- 1,1\}\), where \(V\) is the vertex set of the graph \(G\), with the property that for at least half the vertices \(v \in V\) the sum of the values of \(f\) in \(v\) and in all vertices adjacent to \(v\) is at least 1. The sum of the values of \(f\) in all vertices of \(V\) is called the weight of \(f\). The minimum weight of a majority dominating function on \(G\) is called the majority domination number of \(G\) and denoted by \(\gamma_{\text{maj}} (G)\). In the paper the values of \(\gamma_{\text{maj}}\) are determined for some classes of graphs (complete graphs, circuits, etc.) and \(\gamma_{\text{maj}}\) is related to other numerical invariants concerning domination. It is shown that the problem of deciding, whether there is a majority dominating function of weight \(k\) or less (for a given graph \(G\) and positive integer \(k)\) is NP-complete. Some open problems are presented.