New Polynomial Case for Efficient Domination in P6-free Graphs

In a graph G, an efficient dominating set is a subset D of vertices such that D is an independent set and each vertex outside D has exactly one neighbor in D. The Efficient Dominating Set problem (EDS) asks for the existence of an efficient dominating set in a given graph G, and the Weighted Efficient Dominating Set problem (WEDS) asks for an efficient dominating set of minimum total weight in the given graph G with vertex weight function w on V (G). The (W)EDS is known to be NP-complete for P-7-free graphs, and is known to be polynomial time solvable for P-5-free graphs. However, the computational complexity of the (W) EDS problem is unknown for P-6-free graphs. In this paper, we show that the WEDS problem can be solved in polynomial time for a subclass of P-6-free graphs, namely (P-6, banner)-free graphs, where a banner is the graph obtained from a chordless cycle on four vertices by adding a vertex that has exactly one neighbor on the cycle.