## Abstract

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 F_{3} rooted at a white vertex v adjacent to another white vertex u, which adjacent to a black vertex w. We prove that the F_{3}-domination problem is NP-complete for bipartite planar graphs and for chordal graphs. We also give a linear-time algorithm for the F_{3}-domination problem in trees.

Original language | English |
---|---|

Pages (from-to) | 861-865 |

Number of pages | 5 |

Journal | Information Processing Letters |

Volume | 113 |

Issue number | 22-24 |

DOIs | |

Publication status | Published - 2013 |

Externally published | Yes |

## Keywords

- 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