(1, j)-set problem in graphs

A subset D subset of V of a graph G = (V, E) is a (1, j)-set (Chellali et al., 2013) if every vertex v is an element of V\D is adjacent to at least 1 but not more than j vertices in D. The cardinality of a minimum (1, j)-set of G, denoted as gamma((1,j))(G), is called the (1, j)-domination number of G. In this paper, using probabilistic methods, we obtain an upper bound on gamma((1,j))(G) for j >= 0(log Delta), where Delta is the maximum degree of the graph. The proof of this upper bound yields a randomized linear time algorithm. We show that the associated decision problem is NP-complete for choral graphs but, answering a question of Chellali et al., providea linear-time algorithm for trees for a fixed j. Apart from this, we design a polynomial time algorithm for finding gamma((1,j))(G) for a fixed j in a split graph, and show that (1, j)-set problem is fixed parameter tractable in bounded genus graphs and bounded treewidth graphs. (C) 2016 Elsevier B.V. All rights reserved.