A set Dof vertices in a graph Gis an efficient dominatingset (e.d.s.for short) of Gif Dis an independent set and every vertex not in Dis adjacent to exactly one vertex in D. The efficient domination (ED) problem asks for the existence of an e.d.s.in G. The minimum weighted efficient domination problem (MIN-WED for short) is the problem of finding an e.d.s.of minimum weight in a given vertex-weighted graph. Brandstädt, Fiˇcur, Leitert and Milaniˇc (2015) [3]stated the running times of the fastest known polynomial-time algorithms for the MIN-WED problem on some graphs classes by using a Hasse diagram. In this paper, we update this Hasse diagram by showing that, while for every integer dsuch that d =3kor d =3k +2, where k ≥1, the ED problem remains NP-complete for graphs of diameter d, the weighted version of the problem is solvable in time O(|V(G)|+|E(G)|)in the class of diameter three bipartite graphs and in time O(|V(G)|5)in the class of diameter three planar graphs.

Keywords