Independent [1, k]-Sets in Graphs
Document Type
Article
Publication Date
1-1-2014
Description
A subset S ⊆ V in a graph G = (V,E) is a [1, k]-set for a positive integer k if for every vertex v ∈ V \ S, 1 ≤ |N(v) ∩ S|; ≤ k, that is, every vertex v ∈ V \ S is adjacent to at least one but not more than k vertices in S. We consider [1, k]-sets that are also independent, and note that not every graph has an independent [1, k]-set. For graphs having an independent [1, k]-set, we define the lower and upper [1, k]-independence numbers and determine upper bounds for these values. In addition, the trees having an independent [1, k]-set are characterized. Also, we show that the related decision problem is NP-complete.
Citation Information
Chellali, Mustapha; Favaron, Odile; Haynes, Teresa W.; Hedetniemi, Stephen T.; and McRae, Alice. 2014. Independent [1, k]-Sets in Graphs. Australasian Journal of Combinatorics. Vol.59(1). 144-156. https://ajc.maths.uq.edu.au/pdf/59/ajc_v59_p144.pdf ISSN: 1034-4942