AbstractWe prove that the problem of finding two minimum dominating sets (connected dominating sets or clique transversals) with minimum intersection is polynomially solvable on interval graphs. Furthermore, the problem of deciding whether or not there exist two disjoint minimum dominating sets (connected dominating sets or clique transversals) is shown to be NP-hard for chordal graphs.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory
Additional Key Words and Phrases: chordal graph, interval graph, dominating set, clique transversal
Selected references
- Martin Farber and J. Mark Keil. Domination in permutation graphs. Journal of Algorithms, 6(3):309-321, September 1985.
- Haim Kaplan and Ron Shamir. The domatic number problem on some perfect graph families. Information Processing Letters, 49(1):51-56, 14 January 1994.