On majority domination in graphs

AbstractA majority dominating function on the vertex set of a graph G=(V,E) is a function g:V→{1,−1} such that g(N[v])⩾1 for at least half of the vertices v in V. The weight of a majority dominating function is denoted as g(V) and is ∑g(v) over all v in V. The majority domination number of a graph is the minimum possible weight of a majority dominating function, and is denoted as γmaj(G). We determine the majority domination numbers of certain families of graphs. Moreover, we show that the decision problem corresponding to computing the majority domination number of an arbitrary disjoint union of complete graphs is NP-complete