Algorithmic aspects of majority domination

Hong Gwa Yeh, Gerard J. Chang

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

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
Volume1
Issue number3
DOIs
StatePublished - Sep 1997

Keywords

  • Cograph
  • Majority domination
  • Tree
  • κ-tree

Fingerprint

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

Cite this