A Tight Upper Bound on the Average Order of Dominating Sets of a Graph

Abstract

In this paper we study the the average order of dominating sets in a graph, $\mathrm{avd}(G)$. Like other average graph parameters, the extremal graphs are of interest. Beaton and Brown (2021) conjectured that for all graphs $G$ of order $n$ without isolated vertices, $\mathrm{avd}(G)\le 2n/3$. Recently, Erey (2021) proved the conjecture for forests without isolated vertices. In this paper we prove the conjecture and classify which graphs have $\mathrm{avd}(G)=2n/3$. We also use our bounds to prove the average version of Vizing's Conjecture.