Private Domination Trees

Abstract

For a subset of vertices $S$ in a graph $G$, if $v\in S$ and $w\in V-S$, then the vertex $w$ is an $externalprivateneighborofv$ (with respect to $S$) if the only neighbor of $w$ in $S$ is $v$. A dominating set $S$ is a private dominating set if each $v\in S$ has an external private neighbor. Bollébas and Cockayne (Graph theoretic parameters concerning domination, independence and irredundance. J. Graph Theory $3(1979)241-250)$ showed that every graph without isolated vertices has a minimum dominating set which is also a private dominating set. We define a graph $G$ to be a $privatedominationgraph$ if every minimum dominating set of $G$ is a private dominating set. We give a constructive characterization of private domination trees.