Abstract | ||
---|---|---|
A subset S subset of V in a graph G - (V, E) is a [1, k]-set for a positive integer k if for every vertex v is an element of V \ S, 1 <= |N(v) boolean AND S| <= k, that is, every vertex v is an element of 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. |
Year | Venue | DocType |
---|---|---|
2014 | AUSTRALASIAN JOURNAL OF COMBINATORICS | Journal |
Volume | ISSN | Citations |
59 | 2202-3518 | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mustapha Chellali | 1 | 188 | 38.24 |
Odile Favaron | 2 | 484 | 60.59 |
Teresa W. Haynes | 3 | 774 | 94.22 |
Stephen T. Hedetniemi | 4 | 1575 | 289.01 |
Alice A. McRae | 5 | 163 | 21.29 |