Majority out-dominating functions in digraphs

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 \rightarrow \{-1,1\}\) such...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2013-11
Main Authors: Manrique, Martín, Ebadi, Karam, Azami, Akbar
Format: Article
Language:English
Subjects:
Apexes
Graph theory
Mathematical functions
Minimum weight
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 \rightarrow \{-1,1\}\) such that \(f(N^+[v])\geq1\) 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\limits_{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.
ISSN:2331-8422