Efficient and Excess Domination in Graphs

Abstract

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 $\overline{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)\le \frac{2n}{3}–2$.