Edge domination in graphs (Q1392425): Difference between revisions

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\).