Computing a minimum outer-connected dominating set for the class of chordal graphs

For a graph G = (V, E), a dominating set is a set D subset of V such that every vertex v is an element of V\D has a neighbor in D. Given a graph G = (V, E) and a positive integer k, the minimum outer-connected dominating set problem for G is to decide whether G has a dominating set D of cardinality at most k such that G[V\D] , the induced subgraph by G on V\D, is connected. In this paper, we consider the complexity of the minimum outer-connected dominating set problem for the class of chordal graphs. In particular, we show that the minimum outer-connected dominating set problem is NP-complete for doubly chordal graphs and undirected path graphs, two well studied subclasses of chordal graphs. We also give a linear time algorithm for computing a minimum outer-connected dominating set in proper interval graphs. Notice that proper interval graphs form a subclass of undirected path graphs as well as doubly chordal graphs. Crown Copyright (C) 2013 Published by Elsevier B.V. All rights reserved.