کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419365 | 683793 | 2013 | 9 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: [1, 2]-sets in graphs [1, 2]-sets in graphs](/preview/png/419365.png)
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.
Journal: Discrete Applied Mathematics - Volume 161, Issue 18, December 2013, Pages 2885–2893