The average order of dominating sets of a graph

DOI10.1016/J.DISC.2021.112595MaRDI QIDQ2231709zbMATH OpenOpenAlexFDO

Publication date 30 September 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.06531

average order of dominating sets dominating set domination polynomial

Graph polynomials (05C31) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

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}].

Recommendations

Cites work

Cited in

(12)

This page was built for publication: The average order of dominating sets of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2231709)