EFFICIENT EDGE DOMINATION PROBLEMS IN GRAPHS

It has been shown, recently, that resource allocation problems in para llel processing systems can be viewed as edge domination problems in g raphs. Other applications of edge domination include encoding theory a nd network routing problems. While the existence of efficient edge dom inating sets in special classes of graphs such as paths and cycles can be determined in polynomial time, the complexity of the problem for g eneral graphs remains open. In a graph G = (V, E), an edge uv is-an-el ement-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 fo r trees. In this paper, we show that the problem of determining if a g raph 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-par allel graphs, we show that the problem is polynomial. In fact, we pres ent a linear-time algorithm for calculating the maximum number or edge s that can be efficiently dominated in series-parallel graphs.