2018/05/30 by Andreas Brandstädt, Brandstädt, Andreas, Raffaele Mosca +1
Computer Science · #Advanced Graph Theory Research #Cooperative Communication and Network Coding #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems #cs.DM
paper · pdf · doi:10.48550/arxiv.1806.00386
arXiv admin note: text overlap with arXiv:1701.03414
openalex publication_date 2018/05/30 · arxiv created 2019/07/23 · arxiv updated 2019/07/24 · openalex created_date 2025/10/10 · 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 known to be \NP-complete even for very restricted H-free graph classes such as for 2P3-free chordal graphs while it is solvable in polynomial time for P6-free graphs. Here we focus on H-free bipartite graphs: We show that (weighted) ED can be solved in polynomial time for H-free bipartite graphs when H is P7 or ℓ P4 for fixed ℓ, and similarly for P9-free bipartite graphs with vertex degree at most 3, and when H is S2,2,4. Moreover, we show that ED is \NP-complete for bipartite graphs with diameter at most 6.