2014/07/17 by Andreas Brandstädt, Andreas Brandstadt, Brandstadt, Andreas +2 · 2 citations
Computer Science · #05C85 #68R10 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Cooperative Communication and Network Coding #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #msc:05C85 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1407.4593
arxiv created 2014/07/17 · openalex publication_date 2014/07/17 · arxiv updated 2014/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a finite undirected graph. A vertex \em dominates itself and all its neighbors in G. A vertex set D is an \em efficient dominating set (e.d. 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. in G, is known to be \NP-complete even for very restricted graph classes such as for claw-free graphs, for chordal graphs and for 2P3-free graphs (and thus, for P7-free graphs). We call a graph F a \em linear forest if F is cycle- and claw-free, i.e., its components are paths. Thus, the ED problem remains \NP-complete for F-free graphs, whenever F is not a linear forest. Let WED denote the vertex-weighted version of the ED problem asking for an e.d. of minimum weight if one exists. In this paper, we show that WED is solvable in polynomial time for (P5+kP2)-free graphs for every fixed k, which solves an open problem, and, using modular decomposition, we improve known time bounds for WED on (P4+P2)-free graphs, (P6,S1,2,2)-free graphs, and on (2P3,S1,2,2)-free graphs and simplify proofs. For F-free graphs, the only remaining open case is WED on P6-free graphs.