Edge Dominating Sets in Graphs

Abstract

We prove that the edge dominating set problem for graphs is $NP$-complete even when restricted to planar or bipartite graphs of maximum degree 3. We show as a corollary that the minimum maximal matching and the achromatic number problems are $NP$-complete. A new linear time algorithm for finding minimum independent edge dominating sets in trees is described, based on an observed relationship between edge dominating sets and independent sets in total graphs.