کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427131 | 686455 | 2013 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Algorithmic aspect of stratified domination in graphs Algorithmic aspect of stratified domination in graphs](/preview/png/427131.png)
• The F3F3-domination problem is NP-complete for bipartite planar graphs.
• The F3F3-domination problem is NP-complete for chordal graphs.
• A linear-time algorithm for the F3F3-domination problem in trees.
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)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)γF(G) of G is the minimum cardinality of an F -dominating set. We consider the 3-vertex black-white graph F3F3 rooted at a white vertex v adjacent to another white vertex u, which adjacent to a black vertex w . We prove that the F3F3-domination problem is NP-complete for bipartite planar graphs and for chordal graphs. We also give a linear-time algorithm for the F3F3-domination problem in trees.
Journal: Information Processing Letters - Volume 113, Issues 22–24, November–December 2013, Pages 861–865