On Efficient Domination for Some Classes of H-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 2P3-free chordal graphs while it is solvable in polynomial time for P6-free chordal graphs (and even for P6-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 2P2-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 S1,2,3.
This is joint work with Raffaele Mosca.