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.
| Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-17152 |
| Date | 01 January 2014 |
| Creators | Chellali, Mustapha, Favaron, Odile, 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.0022 seconds