Algorithmic aspect of stratified domination in graphs

Gerard Jennhwa Chang, Chan Wei Chang, David Kuo, Sheung Hung Poon

Research output: Journal PublicationArticlepeer-review

2 Citations (Scopus)


Chartrand, Haynes, Henning and Zhang introduced a variation of domination called stratified domination in graphs. This paper studies stratified domination from an algorithmic point of view. A 2-stratified (or black-white) graph is a graph in which every vertex is colored black or white. Given a black-white graph F rooted at a white vertex v, an F-coloring of a graph G=(V,E) is a black-white coloring of V for which every white vertex v of G belongs to a copy of F (not necessarily induced in G) rooted at v. An F-dominating set of G is the set of all black vertices in an F-coloring. The F-domination number γF(G) of G is the minimum cardinality of an F-dominating set. We consider the 3-vertex black-white graph F3 rooted at a white vertex v adjacent to another white vertex u, which adjacent to a black vertex w. We prove that the F3-domination problem is NP-complete for bipartite planar graphs and for chordal graphs. We also give a linear-time algorithm for the F3-domination problem in trees.

Original languageEnglish
Pages (from-to)861-865
Number of pages5
JournalInformation Processing Letters
Issue number22-24
Publication statusPublished - 2013
Externally publishedYes


  • Bipartite graph
  • Chordal graph
  • Design of algorithms
  • Domination
  • F-domination
  • Graph algorithms
  • k-stratified graph
  • NP-complete
  • Planar graph
  • Tree

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'Algorithmic aspect of stratified domination in graphs'. Together they form a unique fingerprint.

Cite this