Title: Perfect Edge Domination: Hard and Solvable Cases,
Abstract: Let $G$ be an undirected graph. An edge of $G$ dominates itself and all edges
adjacent to it. A subset $E'$ of edges of $G$ is an edge dominating set of $G$,
if every edge of the graph is dominated by some edge of $E'$. We say that $E'$
is a perfect edge dominating set of $G$, if every edge not in $E'$ is dominated
by exactly one edge of $E'$. The perfect edge dominating problem is to
determine a least cardinality perfect edge dominating set of $G$. For this
problem, we describe two NP-completeness proofs, for the classes of claw-free
graphs of degree at most 3, and for bounded degree graphs, of maximum degree at
most $d \geq 3$ and large girth. In contrast, we prove that the problem admits
an $O(n)$ time solution, for cubic claw-free graphs. In addition, we prove a
complexity dichotomy theorem for the perfect edge domination problem, based on
the results described in the paper. Finally, we describe a linear time
algorithm for finding a minimum weight perfect edge dominating set of a
$P_5$-free graph. The algorithm is robust, in the sense that, given an
arbitrary graph $G$, either it computes a minimum weight perfect edge
dominating set of $G$, or it exhibits an induced subgraph of $G$, isomorphic to
a $P_5$.