کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420185 | 683902 | 2012 | 13 صفحه PDF | دانلود رایگان |

Given two sets σ,ρσ,ρ of non-negative integers, a set SS of vertices of a graph GG is (σ,ρ)(σ,ρ)-dominating if |S∩N(v)|∈σ|S∩N(v)|∈σ for every vertex v∈Sv∈S, and |S∩N(v)|∈ρ|S∩N(v)|∈ρ for every v∉Sv∉S. This concept, introduced by Telle in 1990’s, generalizes and unifies several variants of graph domination studied separately before. We study the parameterized complexity of (σ,ρ)(σ,ρ)-domination in this general setting. Among other results, we show that the existence of a (σ,ρ)(σ,ρ)-dominating set of size kk (and at most kk) are W[1]-complete problems (when parameterized by kk) for any pair of finite sets σσ and ρρ. We further present results on dual parameterization by n−kn−k, and results on certain infinite sets (in particular for σ,ρσ,ρ being the sets of even and odd integers).
Journal: Discrete Applied Mathematics - Volume 160, Issue 6, April 2012, Pages 780–792