(1,j)(1,j)-set problem in graphs

A subset D⊆VD⊆V of a graph G=(V,E)G=(V,E) is a (1,j)(1,j)-set   (Chellali et al., 2013) if every vertex v∈V∖Dv∈V∖D is adjacent to at least 1 but not more than jj vertices in DD. The cardinality of a minimum (1,j)(1,j)-set of GG, denoted as γ(1,j)(G)γ(1,j)(G), is called the (1,j)(1,j)-domination number   of GG. In this paper, using probabilistic methods, we obtain an upper bound on γ(1,j)(G)γ(1,j)(G) for j≥O(logΔ)j≥O(logΔ), where ΔΔ 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., provide a linear-time algorithm for trees for a fixed jj. Apart from this, we design a polynomial time algorithm for finding γ(1,j)(G)γ(1,j)(G) for a fixed jj in a split graph, and show that (1,j)(1,j)-set problem is fixed parameter tractable in bounded genus graphs and bounded treewidth graphs.