Two minimum dominating sets with minimum intersection in chordal graphs
Peter Eades, Mark Keil, Paul D Manuel, Mirka Miller · 1996
We prove that the problem of finding two minimum dominating sets (connected dominating sets or vertex clique covers) with minimum intersection is linearly solvable in interval graphs. Furthermore, the problem of deciding whether or not there exist two disjoint minimum dominating sets (connected dominating sets or vertex clique covers) is shown to be NP-hard for chordal graphs. Keywords: vertex clique cover, dominating set, chordal graph. 1 Introduction A graph is said to be chordal if it contains no induced cycle of length 4 or greater. A graph is said to be an interval graph if it is the intersection graph of a family of intervals along the real line. A set S of vertices in a graph G is a dominating set if every vertex, not in S, is adjacent to at least one vertex in S. A dominating set S is a connected dominating set if the subgraph induced by S is connected. A subset A of V is a clique of a graph G if it induces a complete subgraph of G. A clique C is maximal if there is no clique...