Algorithmic aspects of majority domination

Hong Gwa Yeh, Gerard J. Chang

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


This paper studies algorithmic aspects of majority domination, which is a variation of domination in graph theory. A majority dominating function of a graph G = (V, E) is a function g from V to {-1, 1} such that Σu∈N[v] g(u) ≥ 1 for at least half of the vertices v ∈ V. The majority domination problem is to find a majority dominating function g of a given graph G = (V, E) such that Σv∈V g(v) is minimized. The concept of majority domination was introduced by Hedetniemi and studied by Broere et al., who gave exact values for the majority domination numbers of complete graphs, complete bipartite graphs, paths, and unions of two complete graphs. They also proved that the majority domination problem is NP-complete for general graphs; and asked if the problem NP-complete for trees. The main result of this paper is to give polynomial-time algorithms for the majority domination problem in trees, cographs, and k-trees with fixed k.

Original languageEnglish
Pages (from-to)343-350
Number of pages8
JournalTaiwanese Journal of Mathematics
Issue number3
StatePublished - Sep 1997


  • Cograph
  • Majority domination
  • Tree
  • κ-tree


Dive into the research topics of 'Algorithmic aspects of majority domination'. Together they form a unique fingerprint.

Cite this