2015/02/28 by Andreas Brandstädt, Brandstädt, Andreas, Elaine M. Eschen +3 · 2 citations
Computer Science · #Advanced Graph Theory Research #Interconnection Networks and Systems #cs.DM
paper · pdf · doi:10.48550/arxiv.1503.00091
arxiv created 2015/02/28 · arxiv updated 2015/03/03
Let G be a finite undirected graph. A vertex \em dominates itself and all its neighbors in G. A vertex set D is an \em efficient dominating set (e.d. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d. in G, is known to be \NP-complete even for very restricted graph classes such as P7-free chordal graphs. The ED problem on a graph G can be reduced to the Maximum Weight Independent Set (MWIS) problem on the square of G. The complexity of the ED problem is an open question for P6-free graphs and was open even for the subclass of P6-free chordal graphs. In this paper, we show that squares of P6-free chordal graphs that have an e.d. are chordal; this even holds for the larger class of (P6, house, hole, domino)-free graphs. This implies that ED/WeightedED is solvable in polynomial time for (P6, house, hole, domino)-free graphs; in particular, for P6-free chordal graphs. Moreover, based on our result that squares of P6-free graphs that have an e.d. are hole-free and some properties concerning odd antiholes, we show that squares of (P6, house)-free graphs ((P6, bull)-free graphs, respectively) that have an e.d. are perfect. This implies that ED/WeightedED is solvable in polynomial time for (P6, house)-free graphs and for (P6, bull)-free graphs (the time bound for (P6, house, hole, domino)-free graphs is better than that for (P6, house)-free graphs). The complexity of the ED problem for P6-free graphs remains an open question.