A study on the weighted efficient domination problem for \(C_4\)-free bipartite graphs
<p>A vertex set <span class="math inline">\(D\)</span> in a finite undirected graph <span class="math inline">\(G\)</span> is an <span><em>efficient dominating set</em></span> (<em>e.d.s.</em> for short) of <span class="math inline">\(G\)</span> if every vertex of <span class="math inline">\(G\)</span> is dominated by exactly one vertex of <span class="math inline">\(D\)</span>. The <em>Efficient Domination</em> (ED) problem asks for the existence of an e.d.s. in <span class="math inline">\(G\)</span>. The <span><em>Weighted Efficient Dominating Set</em></span> (<span>WED</span> for short) problem further asks for an e.d.s. of minimum/maximum weight in a given graph <span class="math inline">\(G\)</span>. The ED problem is known to be NP-complete, even for claw-free graphs, for <span class="math inline">\(P_7\)</span>-free graphs, for chordal bipartite graphs, for planar bipartite graphs of maximum degree 3 and girth at least <span class="math inline">\(g\)</span> for every fixed <span class="math inline">\(g\)</span>, and thus for <span class="math inline">\(C_4\)</span>-free bipartite graphs. This manuscript reports a study on the WED problem for <span class="math inline">\(C_4\)</span>-free bipartite graphs (in the context of a study for bipartite graphs) and shows that the WED problem can be solved in polynomial time for (<span class="math inline">\(S_{1,2,5},C_4\)</span>)-free bipartite graphs, for (<span class="math inline">\(P_{10},C_4\)</span>)-free bipartite graphs, and for some related graphs classes.</p>