Perfect Domination in Random Graphs

Abstract

For a wide range of $p$, we show that almost every graph $Gϵ\mathcal{G}(n,p)$ has no perfect dominating set and for almost every graph $Gϵ\mathcal{G}(n,p)$ we bound the cardinality of a set of vertices which can be perfectly dominated. We also show that almost every tree $Tϵ\mathcal{T}(n)$ has no perfect dominating set.