For a graph $G = (V, E)$ with vertex set $V$ and edge set $E$, a subset $F$ of $E$ is called an $\emph{ edge dominating set}$ (resp. a $\emph{ total edge dominating set}$) if every edge in $E\backslash F$ (resp. in $E$) is adjacent to at least one edge in $F$, the minimum cardinality of an edge dominating set (resp. a total edge dominating set) of $G$ is the { \em edge domination number} (resp. { \em total edge domination number}) of $G$, denoted by $\gamma^{ '}(G)$ (resp. $\gamma_t^{ '}(G)$). In the present paper, we prove that the total edge domination problem is NP-complete for bipartite graphs with maximum degree 3. We also design a linear-time algorithm for solving this problem for trees. Finally, for a graph $G$, we give the inequality $\gamma^{ '}(G)\leqslant \gamma^{ '}_{ t}(G)\leqslant 2\gamma^{ '}(G)$ and characterize the trees $T$ which obtain the upper or lower bounds in the inequality.
Categories: math.CO