On efficient domination for some classes of [formula omitted]-free chordal graphs.

A vertex set D in a finite undirected graph G is an efficient dominating set (e.d.s 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.s. in G , is known to be NP -complete even for very restricted graph classes such as for 2 P 3 -free chordal graphs while it is solvable in polynomial time for P 6 -free chordal graphs (and even for P 6 -free graphs). A standard reduction from the NP -complete Exact Cover problem shows that ED is NP -complete for a very special subclass of chordal graphs generalizing split graphs. The reduction implies that ED is NP -complete e.g. for double-gem-free chordal graphs while it is solvable in linear time for gem-free chordal graphs (by various reasons such as bounded clique-width, distance-hereditary graphs, chordal square etc.), and ED is NP -complete for butterfly-free chordal graphs while it is solvable in linear time for 2 P 2 -free graphs. We show that (weighted) ED can be solved in polynomial time for H -free chordal graphs when H is net, extended gem, or S 1 , 2 , 3. [ABSTRACT FROM AUTHOR]