MINIMUM EDGE DOMINATING SETS

Let G = (V, E) be a finite undirected graph with n vertices and m edges. A minimum edge dominating set of G is a set of edges D, of smallest cardinality gamma'(G), such that each edge of E - D is adjacent to some edge of D. Let S(G) be the subdivision graph of G and let T(G) be the total graph of G. Let alpha(G) be the stability number of G (cardinality of a largest stable set) and let alpha2(G) be the 2-stability number of G (cardinality of a largest set of vertices in G, no two of which are joined by a path of length 2 or less). The following results are obtained. For any G, gamma'(S(G)) + alpha2(G) = n and 2gamma'(T(G)) + alpha(T(G)) = n + m or n + m + 1. Also, for any depth-first search tree S of G, gamma'(S)/2 less-than-or-equal-to gamma'(G) less-than-or-equal-to 2gamma'(S), and these bounds are tight. The edge domination problem is NP-complete for planar bipartite graphs, their subdivision, line, and total graphs, perfect claw-free graphs. and planar cubic graphs. The stable set problem and the edge domination problem are NP-complete for iterated total graphs. The edge domination problem is solvable in O(n3) time for claw-free chordal graphs, locally connected claw-free graphs, the line graphs of total graphs, the line graphs of chordal graphs, the line graph of any graph in which each nonbridge edge is in a triangle, and the total graphs of any of the preceding graphs.