Menu
Each vertex of a graph \(G = (V, E)\) dominates every vertex in its closed neighborhood. A set \(S \subset V\) is a dominating set if each vertex in \(V\) is dominated by at least one vertex of \(S\), and is an \emph{efficient dominating set} if each vertex in \(V\) is dominated by exactly one vertex of \(S\).
The domination excess \(de(G)\) is the smallest number of times that the vertices of \(G\) are dominated more than once by a minimum dominating set.
We study graphs having efficient dominating sets. In particular, we characterize such coronas and caterpillars, as well as the graphs \(G\) for which both \(G\) and \(\bar{G}\) have efficient dominating sets.
Then we investigate bounds on the domination excess in graphs which do not have efficient dominating sets and show that for any tree \(T\) of order \(n\),
\(de(T) \leq \frac{2n}{3} – 2\).