A subset S⊆V in a graph G=(V,E) is a [j,k]-set if, for every vertex vεV\-S, j≤|N(v)\∩S|≤k for non-negative integers j and k, that is, every vertex vεV\-S is adjacent to at least j but not more than k vertices in S. In this paper, we focus on small j and k, and relate the concept of [j,k]-sets to a host of other concepts in domination theory, including perfect domination, efficient domination, nearly perfect sets, 2-packings, and k-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 G, the restrained domination number is equal to the domination number of G.
| Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-15953 |
| Date | 01 December 2013 |
| Creators | Chellali, Mustapha, Haynes, Teresa W., Hedetniemi, Stephen T., McRae, Alice |
| Publisher | Digital Commons @ East Tennessee State University |
| Source Sets | East Tennessee State University |
| Detected Language | English |
| Type | text |
| Source | ETSU Faculty Works |
Page generated in 0.0018 seconds