A note on efficient domination in a superclass of P5-free graphs

In a graph G = (V, E), an efficient dominating set is a subset D subset of V such that D is an independent set such that each vertex outside D has exactly one neighbor in D. E stands for the graph with vertices a, b, c, d, e, f and edges ab, bc, cd, de and cf, while xNet stands for the graph with vertices a, b,c,d, e, f, g and edges ad, be, cf, de, ef, fd and cg. This note shows that, given an (E, xNet)-free graph, a minimum efficient dominating set (if any) can be found in polynomial time, extending two polynomially solvable cases for efficient dominating sets recently found by Milanic (2013) [4], and Brandstadt et al. (2013) [2]. (C) 2014 Elsevier B.V. All rights reserved.