Efficient edge domination problems in graphs (Q1313728)

In a graph \(G=(V,E)\), an edge \(uv\in E\) is said to dominate itself and any edge \(ux\) or \(vx\) in \(E\), where \(x\in V\). An efficient edge dominating set for the graph \(G\) is a subset \(E'\subseteq E\) such that all edges in \(E\) are dominated by exactly one edge in \(E'\). It is proved that the efficient edge domination problem is NP-complete for general graphs and also for line graphs. The authors define a series-parallel graph \(G\), denoted by \((G,(u,v))\), to be a graph which has no subgraph homeomorphic to the complete graph \(K_ 4\) and which has two distinguished vertices \(u\) and \(v\) denoted as the left and right terminal of \(G\), respectively. They describe an algorithm which computes the maximum number of edges that can be efficiently dominated in a series-parallel graph in \(O(n)\) time where \(n=| V|\).