Edge domination in graphs. (English) Zbl 0906.05032

Arumugam, S.; Velammal, S.

Taiwanese J. Math. 2, No. 2, 173-179 (1998).

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

Reviewer: B.Zelinka (Liberec)

MSC:

05C35	Extremal problems in graph theory
05C05	Trees

Keywords:

edge dominating set; edge domination number; edge domatic number