2020/08/10 by Andreas Brandstädt, Brandstädt, Andreas, Raffaele Mosca +1 · 2 citations
Computer Science · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems #cs.DM
paper · pdf · doi:10.48550/arxiv.2008.04046
openalex publication_date 2020/08/10 · arxiv created 2022/01/03 · arxiv updated 2022/01/04 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
A vertex set D in a finite undirected graph G is an \em 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 G, is \NP-complete for various H-free bipartite graphs, e.g., Lu and Tang showed that ED is \NP-complete for chordal bipartite graphs and for planar bipartite graphs; actually, ED is \NP-complete even for planar bipartite graphs with vertex degree at most 3 and girth at least g for every fixed g. Thus, ED is \NP-complete for K1,4-free bipartite graphs and for C4-free bipartite graphs. In this paper, we show that ED can be solved in polynomial time for S1,3,3-free bipartite graphs.