On majority domination in graphs (Q5946744)

A majority dominating function on the vertex set of a graph \(G=(V,E)\) is a function \(g\colon V\mapsto\{1,-1\}\) such that \(\sum_{u\in N[v]} g(u) \geq 1\) for at least half of the vertices \(v\) in \(V\). The majority domination number \(\gamma_{\text{maj}}(G)\) of a graph \(G\) is defined as \[ \gamma_{\text{maj}}( G)=\min \left\{\sum_{v\in V} g(v): g\text{ is a majority dominating function on }V\right\}. \] The majority domination number has been determined for certain families of graphs in \textit{I. Broere} et al. [Discrete Math. 138, No. 1-3, 125-135 (1995; Zbl 0820.05037)]. Using different counting technique the author generalizes results from the above-mentioned paper and determines \(\gamma_{\text{maj}}(G)\) for some other families of graphs, mostly composed of complete graphs and their complements. In the above-mentioned paper, it has also been shown that the problem of deciding whether \(\gamma_{\text{maj}}(G) \leq k\) for a given graph \(G\) and positive \(k\) is NP-complete. Here the author shows that the problem remains NP-complete even when \(G\) is the disjoint union of complete graphs.