[1, 2]-Sets in Graphs

Creator(s)

Mustapha Chellali, Université Saad Dahlab de Blida
Teresa W. Haynes, East Tennessee State UniversityFollow
Stephen T. Hedetniemi, Clemson University
Alice McRae, Appalachian State University

Document Type

Article

Publication Date

12-1-2013

Description

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.

Citation Information

Chellali, Mustapha; Haynes, Teresa W.; Hedetniemi, Stephen T.; and McRae, Alice. 2013. [1, 2]-Sets in Graphs. Discrete Applied Mathematics. Vol.161(18). 2885-2893. https://doi.org/10.1016/j.dam.2013.06.012 ISSN: 0166-218X