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.