Majority out-dominating functions in digraphs

Abstract

At least two different notions have been published under the name "majority domination in graphs": Majority dominating functions and majority dominating sets. In this work we extend the former concept to digraphs. Given a digraph $D=(V,A),$ a function $f:V\to \{-1,1\}$ such that $f(N^{+}[v])\ge 1$ for at least half of the vertices $v$ in $V$ is a majority out-dominating function (MODF) of $D.$ The weight of a MODF $f$ is $w(f)=\sum _{v\in V}f(v),$ and the minimum weight of a MODF in $D$ is the majority out-domination number of $D,$ denoted ${\gamma }_{maj}^{+}(D).$ In this work we introduce these concepts and prove some results regarding them, among which the fact that the decision problem of finding a majority out-dominating function of a given weight is NP-complete.

arXiv comment12 pages, 2 figures

References in corpus (1)

• Majority out-dominating sets in digraphs

Cited by in corpus (1)

• Majority out-dominating sets in digraphs