2021/01/05 by Andreas Brandstädt, Brandstädt, Andreas, Raffaele Mosca +1 · 1 citation
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM
paper · pdf · doi:10.48550/arxiv.2101.01772
arXiv admin note: text overlap with arXiv:2010.16076
arxiv created 2021/04/14 · arxiv updated 2021/04/15
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 for P7-free graphs, and even for very restricted H-free bipartite graph classes such as for K1,4-free bipartite graphs as well as for C4-free bipartite graphs while it is solvable in polynomial time for P7-free bipartite graphs as well as for S2,2,4-free bipartite graphs. Here we show that ED can be solved in polynomial time for P8-free bipartite graphs.