On majority domination in graphs

DOI10.1016/S0012-365X(00)00370-8MaRDI QIDQ5946744zbMATH OpenOpenAlexFDO

Authors Tara S. Holm

Publication date 19 March 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(00)00370-8

zbMATH Keywords

extremal problemsgraph algorithmsmajority dominationNP-completeness

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

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 NEWLINE\[NEWLINE \gamma_{\text{maj}}( G)=\min \left\{\sum_{v\in V} g(v): g\text{ is a majority dominating function on }V\right\}. NEWLINE\]NEWLINE 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. NEWLINENEWLINENEWLINEIn 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.

Recommendations

• Majority domination in graphs
• scientific article; zbMATH DE number 6889673
• On majority total domination in graphs
• On majority total domination in graphs
• scientific article; zbMATH DE number 1792629
• Upper majority domination number of a graph
• Algorithmic aspects of majority domination
• scientific article; zbMATH DE number 6731937
• Algorithms and complexity of signed, minus, and majority domination
• scientific article; zbMATH DE number 1109393

Cited in

(17)

• Algorithmic aspects of majority domination
• The majority strategy on graphs
• Upper majority domination number of a graph
• Majority domination in graphs
• Majority reinforcement number
• On signed majority total domination in graphs
• Algorithms and complexity of signed, minus, and majority domination
• Signed and minus dominating functions in graphs
• scientific article; zbMATH DE number 6889673 (Why is no real title available?)
• Majority bad number
• Majority Roman domination in graphs
• Network majority on tree topological network
• scientific article; zbMATH DE number 6731937 (Why is no real title available?)
• Dominating functions with integer values in graphs—a survey
• The power of small coalitions under two-tier majority on regular graphs
• Some results on majority bad number
• Majority double Roman domination in graphs

This page was built for publication: On majority domination in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5946744)