New Probabilistic Upper Bounds on the Domination Number of a Graph

Abstract

A subset $S$ of vertices of a graph $G$ is a dominating set of $G$ if every vertex in $V(G)-S$ has a neighbor in $S$. The domination number $\gamma(G)$ of $G$ is the minimum cardinality of a dominating set of $G$. In this paper, we obtain new (probabilistic) upper bounds for the domination number of a graph, and improve previous bounds given by Arnautov (1974), Payan (1975), and Caro and Roditty (1985) for any graph, and Harant, Pruchnewski and Voigt (1999) for regular graphs.