On efficient domination for some classes of H-free bipartite graphs

A vertex set D in a finite undirected graph G is an efficient dominating set (e.d.s. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d.s. in C, is known to be NP-complete even for very restricted H-free graph classes such as for 2P(3)-free chordal graphs while it is solvable in polynomial time for P-6-free graphs. Here we focus on bipartite graphs: We show that (weighted) ED can be solved in polynomial time for H-free bipartite graphs when H is P-7 or lP(4) for fixed l, and similarly for P-9-free bipartite graphs with vertex degree at most 3, and when H is S-2,S-2,S-4 . Moreover, we show that ED is NP-complete for bipartite graphs with diameter at most 6. (C) 2019 Elsevier B.V. All rights reserved.