EFFICIENT EDGE DOMINATION PROBLEMS IN GRAPHS

It has been shown, recently, that resource allocation problems in parallel processing systems can be viewed as edge domination problems in graphs. Other applications of edge domination include encoding theory and network routing problems. While the existence of efficient edge dominating sets in special classes of graphs such as paths and cycles can be determined in polynomial time, the complexity of the problem for general graphs remains open. In a graph G = (V, E), an edge uv is-an-element-of E is said to dominate itself and any edge ux or vx where x is-an-element-of V. A subset of edges E' subset-or-equal-to E is called an efficient edge dominating set for the graph G if all edges in E are dominated by exactly one edge of E'. It is clear that not all graphs have efficient edge dominating sets. In fact, this is not even true for trees. In this paper, we show that the problem of determining if a graph G has an efficient edge dominating set is NP-complete for general graphs as well as for line graphs. However, in the case of series-parallel graphs, we show that the problem is polynomial. In fact, we present a linear-time algorithm for calculating the maximum number or edges that can be efficiently dominated in series-parallel graphs.