On independent [1,k]-set in graphs

Abstract

For an integer k >=1, a subset S V in a graph G = (V,E) is
an independent [1,k]-set of G if S is independent and every vertex in
V-S is adjacent to one but no more than k vertices in S, The upper
[1,k]-independence number noted gamma[1,k](G) is the maximum cardinality of an independent [1,k]-set of G. In this paper, we provide a constructive characterization of graphs having an independent [1,k]-set,
while for split graphs, a necessary and su¢ cient condition is given for
those having an independent [1,k]-set. Moreover, some upper bounds
on gamma[1,k](G) are established for graphs having an independent [1,k]-set. We also establish a Nordhaus-Gaddum type result for the upper
[1,k]-independence number, where in addition, a characterization of
extremal graphs attaining each bound is provided. Finally, we show
that the decision problem corresponding to the problem of computing
the upper [1,k]-independence number is NP-complete for bipartite and
chordal graphs.