Weighted Efficient Domination for $P_5$-Free Graphs in Linear Time

Abstract

In a finite undirected graph $G=(V,E)$, a vertex $v\in V$ {\em dominates} itself and its neighbors. A vertex set $D\subseteq 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 $P_7$-free graphs but solvable in polynomial time for $P_5$-free graphs. Very recently, it has been shown by Lokshtanov et al. and independently by Mosca that ED is solvable in polynomial time for $P_6$-free graphs. In this note, we show that, based on modular decomposition, ED is solvable in linear time for $P_5$-free graphs.

References in corpus (3)

• Weighted Efficient Domination for $(P_5+k{P}_2)$-Free Graphs in Polynomial Time
• New Polynomial Cases of the Weighted Efficient Domination Problem
• Efficient Domination for Some Subclasses of $P_6$-Free Graphs in Polynomial Time

Cited by in corpus (1)

• Weighted Efficient Domination for $P_6$-Free Graphs in Polynomial Time