On \([j, k]\)-sets in graphs (Q2091155)

For postive integers \(j\) and \(k\) with \(j\leq k\), a vertex subset \(S\) of a graph \(G\) is called a \([j,k]\)-set if every vertex in \(V(G)\setminus S\) is adjacent at least \(j\) elements in \(S\) but no more than \(k\) elements in \(S\). The \([j,k]\)-domination number \(\gamma_{[j,k]}(G)\) is the minimum cardinality of a \([j,k]\)-set in \(G\). The special cases when \(j=1\) and \(k=2\), and \(j=1\) were extensively studied. In this paper, the authors show that the decision problem is NP-complete whether or not there exists a \([j,k]\)-set of cardinality at most \(p\) in a graph \(G\) with at least \(p\) vertices. In addition, some sufficient conditions for which a graph has \(\gamma_{[j,k]}(G)\in\{n-1, n\}\) are presented.