Perfect edge domination and efficient edge domination in graphs (Q1613347): Difference between revisions

Consider an undirected graph \(G=(V,E)\). An edge \(e\in E\) is said to dominate itself and any edge that shares an endpoint. A set of edges \(D\subseteq E\) is a perfect edge dominating set, respectively efficient edge dominating set, if every edge of \(E-D\), respectively of \(E\) is dominated by exactly one edge in \(D\). This paper considers the problem to find perfect or efficient dominating sets in given graphs of minimum size. It is shown that the perfect (efficient) edge dominating set problem is NP-complete on bipartite (planar bipartite) graphs. The generalizations with edge weights is shown to be linear time solvable on chordal graphs, and on generalized series-parallel graphs. The result on generalized series-parallel graphs can be obtained without much work as a consequence on earlier work on treewidth. Generalized series-parallel graphs have treewidth two, and the (weighted) perfect and efficient edge dominating set problems can be expressed in extended monadic second-order logic, and hence the result of \textit{S. Arnborg, J. Lagergren} and \textit{D. Seese} [J. Algorithms 12, 308-340 (1991; Zbl 0734.68073)] can be used to show that these problems are linear time solvable on graphs of bounded treewidth and hence series-parallel graphs.