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

Abstract

A subset $D\subseteq V$of a graph $G=(V,E)$ is a $(1,j)$-set if every vertex $v\in V\setminus 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$. Given a graph $G=(V,E)$ and an integer $k$, the decision version of the $(1,j)$-set problem is to decide whether $G$ has a $(1,j)$-set of cardinality at most $k$. In this paper, we first obtain an upper bound on ${\gamma }_{(1,j)}(G)$ using probabilistic methods, for bounded minimum and maximum degree graphs. Our bound is constructive, by the randomized algorithm of Moser and Tardos [MT10], We also show that the $(1,j)$- set problem is NP-complete for chordal graphs. Finally, we design two algorithms for finding ${\gamma }_{(1,j)}(G)$ of a tree and a split graph, for any fixed $j$, which answers an open question posed in [CHHM13].

Cited by in corpus (1)

• Perfect and quasiperfect domination in trees