A Generalization of maximal independent sets

We generalize the concept of maximal-independent set in the following way. For a nonnegative integer k we define a k-insulated set of a graph G as a s ubset S of its vertices such that each vertex in S is adjacent to at most k other vertices in S and each vertex not in S is adjacent to at least k+1 v ertices in S. We show that it is NP-hard to approximate a maximum k-insulat ed set within a polynomial factor and describe a polynomial algorithm which approximates a maximum k-insulated set in an n-vertex graph to within the factor of cnk/log(2)n, for a constant c > 0. We also give an O(kn(2)) algor ithm which finds an arbitrary k-insulated set. (C) 2001 Elsevier Science B. V. All rights reserved.