The average order of dominating sets of a graph (Q2231709)

A dominating set in a graph is a set of vertices such that every vertex of the graph is either in the set or has a neighbour in the set. In this paper the authors initiate the study of the average order of dominating sets in a graph \(G\), denoted by \(\mathrm{avd}(G)\) and defined as the average cardinality of a dominating set in \(G\). They show that the maximum and the minimum average order of dominating sets over all graphs of order \(n\) is achieved uniquely by the edgeless and the complete graph, respectively. For graphs without isolated vertices, they give an upper bound on the average order of dominating sets in terms of the order and the minimum degree. The bound implies that the average order of dominating sets in an \(n\)-vertex graph without isolated vertices is at most \(3n/4\). Another upper bound is given in terms of the degree sequence and, as a corollary, an upper bound of \(\frac{n}{2}\left(1+\frac{\delta}{2^\delta-1}\right)\) is derived where \(\delta\ge 1\) is the minimum degree. The authors pose an interesting conjecture stating that the average order of dominating sets in a connected \(n\)-vertex graph with \(n\ge 2\) is at most \(2n/3\). They show that this bound can be achieved for all \(n\ge 2\) and provide some evidence for the conjecture, by establishing it for graphs with minimum degree at least 4 and for quasi-regularizable graph, that is, graphs where one can replace each edge with a non-negative integer number of parallel copies, so as to obtain a regular multigraph of positive degree. Furthermore, they prove an upper bound on the average order of dominating sets in terms of the order and the matching number of the graph. Using a connection with double dominating sets, the authors establish a tight lower bound for the average order of dominating sets of an \(n\)-vertex tree and show that the bound is achieved only by the stars (that is, graphs isomorphic to the complete bipartite graph \(K_{1,n-1}\)). They also study a normalized version of the parameter \(\mathrm{avd}(G)\), defined as \(\widehat{\mathrm{avd}}(G) = \mathrm{avd}(G)/|V(G)|\). They compute the limit of this parameter for paths \(P_n\) and cycles \(C_n\), as \(n\to\infty\), show that the set all possible values of \(\widehat{\mathrm{avd}}(G)\) is dense in the interval \([1/2,1]\), and show that for every edge probability \(p\in (0,1)\), the Erdős-Renyi random graph \(G(n,p)\) satisfies the inequalities \(1/2\le \widehat{\mathrm{avd}}(G(n,p))\le 1/2+1/(2n)\) asymptotically almost surely. In the meantime, the conjecture on the upper bound of \(2n/3\) for connected graphs has been proved for trees by \textit{A. Erey} [Discrete Math. 346, No. 1, Article ID 113127, 7 p. (2023; Zbl 1502.05186)]. A proof of the conjecture for general graphs was also announced, in the more general context of graphs without isolated vertices, by \textit{I. Beaton} and \textit{B. Cameron} [``A tight upper bound on the average order of dominating sets of a graph'', Preprint, \url{arXiv:2208.10475}].