[1, 2]-sets in graphs

A subset S⊆VS⊆V in a graph G=(V,E)G=(V,E) is a [j,k][j,k]-set if, for every vertex v∈V∖Sv∈V∖S, j≤|N(v)∩S|≤kj≤|N(v)∩S|≤k for non-negative integers jj and kk, that is, every vertex v∈V∖Sv∈V∖S is adjacent to at least jj but not more than kk vertices in SS. In this paper, we focus on small jj and kk, and relate the concept of [j,k][j,k]-sets to a host of other concepts in domination theory, including perfect domination, efficient domination, nearly perfect sets, 2-packings, and kk-dependent sets. We also determine bounds on the cardinality of minimum [1, 2]-sets, and investigate extremal graphs achieving these bounds. This study has implications for restrained domination as well. Using a result for [1, 3]-sets, we show that, for any grid graph GG, the restrained domination number is equal to the domination number of GG.