A Quadratic-Time Algorithm for Isolate Domination in Trees

For a graph G with vertex set V, a set $$S\subseteq V$$ is called a dominating set of G if every vertex in $$V-S$$ has a neighbor in S. If the set $$S\subseteq V$$ is a dominating set of G and the induced subgraph G[S] contains at least one isolated vertex, the set S is called an isolate dominating set of G. The minimum cardinality of a dominating set of G is called the domination number of G, denoted by $$\gamma (G)$$ , and the minimum cardinality of an isolate dominating set of G is called the isolate domination number of G, denoted by $$\gamma _0(G)$$ . It has been proved that the isolate domination problem is NP-complete in general. In this paper, we present a quadratic-time algorithm to compute the isolate domination number of a tree.