2015/07/24 by Andreas Brandstädt, Andreas Brandstadt, Brandstadt, Andreas
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #cs.DM
paper · pdf · doi:10.48550/arxiv.1507.06765
arxiv created 2015/07/24 · openalex publication_date 2015/07/24 · arxiv updated 2015/07/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a finite undirected graph G=(V,E), a vertex v ∈ V \em dominates itself and its neighbors. A vertex set D ⊆ V in G is an \em efficient dominating set (\em e.d. for short) of G if every vertex of G is dominated by exactly one vertex of D. The \em Efficient Domination (ED) problem, which asks for the existence of an e.d. in G, is known to be NP-complete for P7-free graphs but solvable in polynomial time for P5-free graphs. Very recently, it has been shown by Lokshtanov et al. and independently by Mosca that ED is solvable in polynomial time for P6-free graphs. In this note, we show that, based on modular decomposition, ED is solvable in linear time for P5-free graphs.