Weighted efficient domination in two subclasses of P6P6-free graphs

In a graph GG, an efficient dominating set   is a subset DD of vertices such that DD is an independent set and each vertex outside DD has exactly one neighbor in DD. The Efficient Dominating Set (ED) problem asks for the existence of an efficient dominating set in a given graph. The ED problem is known to be solvable in polynomial time for P5P5-free graphs but NPNP-complete for P7P7-free graphs whereas for P6P6-free graphs, its complexity was an open problem. Recently, Lokshtanov et al. and independently, Mosca showed that ED is solvable in polynomial time for P6P6-free graphs.In this paper, we show that the ED problem can be solved efficiently for two subclasses of P6P6-free graphs, namely for (P6P6, bull)-free graphs, and for (P6,S1,1,3P6,S1,1,3)-free graphs; the time bounds for the two subclasses are much better than in the general case of P6P6-free graphs.