## Edge domination in graphs.(English)Zbl 0906.05032

An edge dominating set in a graph $$G$$ is a subset $$X$$ of the edge set $$E(G)$$ of $$G$$ such that each edge of $$G$$ either is in $$X$$, or has a common end vertex with an edge of $$X$$. The edge domination number $$\gamma'(G)$$ of $$G$$ is the minimum number of edges of an edge dominating set in $$G$$. The maximum number of classes of a partition of $$E(G)$$ into edge dominating sets is the edge domatic number $$d'(G)$$ of $$G$$. The paper characterizes graphs $$G$$ for which $$\gamma'(G)= p/2$$ and graphs $$G$$ for which $$\gamma'(G)+ d'(G)= q+1$$, where $$p$$ is the number of vertices and $$q$$ is the number of edges of $$G$$. Further, trees and unicyclic graphs with $$\gamma'(G)= \lfloor p/2\rfloor$$ and $$\gamma'(G)= q-\Delta'$$ are characterized, where $$\Delta'$$ is the maximum degree of an edge of $$G$$.

### MSC:

 05C35 Extremal problems in graph theory 05C05 Trees
Full Text: