Weighted Efficient Domination in Classes of P₆-free Graphs

Original · EN

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 Minimum Weight Efficient Dominating Set (Min-WED) problem asks for an efficient dominating set of total minimum weight in a given vertex-weighted graph; the Maximum Weight Efficient Dominating Set (Max-WED) problem is defined similarly. The Min-WED/Max-WED is known to be NP-complete for P₇-free graphs, and is known to be polynomial time solvable for P₅-free graphs. However, the computational complexity of the Min-WED/Max-WED problem is unknown for P₆-free graphs. In this paper, we show that the Min-WED/Max-WED problem can be solved in polynomial time for two subclasses of P₆-free graphs, namely for (P₆,S₁,₁,₃)-free graphs, and for (P₆, bull)-free graphs.