On $[1,2]$-Domination in Interval and Circle Graphs

A subset S of vertices in a graph $G=(V, E)$ is Dominating Set if each vertex in V(G) S is adjacent to at least one vertex in S. Chellali et al. in 2013, by restricting the number of neighbors in S of a vertex outside S, introduced the concept of $[1,j]$-dominating set. A set D ⊆ V of a graph $G = (V, E)$ is called $[1,j]$-Dominating Set of G if every vertex not in D has at least one neighbor and at most j neighbors in D. The Minimum $[1,j]$-Domination problem is the problem of finding the minimum set D. Given a positive integer k and a graph $G = (V, E)$, the $[1,j]$-Domination Decision problem is to decide whether G has $[1,j]$-dominating set of cardinality at most k. A polynomial-time algorithm was obtained in split graphs for a constant j in contrast to the classic Dominating Set problem which is NP-hard in split graphs. This result motivates us to investigate the effect of restriction j on the complexity of $[1,j]$-domination problem on various classes of graphs. Although for j≥ 3, it has been proved that the minimum of classical domination is equal to minimum $[1,j]$-domination in interval graphs, the complexity of finding the minimum $[1,2]$-domination in interval graphs is still outstanding. In this paper, we propose a polynomial-time algorithm for computing a minimum $[1,2]$ on non-proper interval graphs by a dynamic programming technique. Next, on the negative side, we show that the minimum $[1,2]$-dominating set problem on circle graphs is $NP$-complete.