New probabilistic upper bounds on the domination number of a graph (Q2318775)

Summary: 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 \textit{V. I. Arnautov} [Prikl. Mat. Programm. 11, 3--8 (1974; Zbl 0297.05131)], \textit{C. Payan} [Cah. Cent. Étud. Rech. Opér. 17, 307--317 (1975; Zbl 0341.05126)], and \textit{Y. Caro} and \textit{Y. Roditty} [Ars Comb. 20, 167--180 (1985; Zbl 0623.05031)] for any graph, and \textit{J. Harant} et al. [Comb. Probab. Comput. 8, No. 6, 547--553 (1999; Zbl 0959.05080)] for regular graphs.