Majority out-dominating functions in digraphs

2013/11/03 by Martín Manrique, Manrique, Martín, Karam Ebadi +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1311.0475

12 pages, 2 figures

arxiv created 2013/11/03 · arxiv updated 2013/11/05

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 → \-1,1\ such that f(N⁺[v])≥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)=∑_{v∈ V}f(v), and the minimum weight of a MODF in D is the majority out-domination number of D, denoted γ⁺_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.

Related

• Majority out-dominating sets in digraphs
• Further Results on the Majority Roman Domination in graphs
• Majority Digraphs
• Domination and fractional domination in digraphs
• Complexity Dichotomies for the Maximum Weighted Digraph Partition Problem