Minimum Edge Dominating Sets

Source abstract

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 $\alpha _2 ( 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 ) ) + \alpha _2 ( G ) = n$ and $2\gamma ' ( T ( G ) ) + \alpha ( T ( G ) ) = n + m$ or $n + m + 1$. Also, for any depth-first search tree S of $G,\gamma ' ( S )/2\leqq \gamma ' ( G )\leqq 2\gamma ' (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( n^3 )$ 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.