The Average Order of Dominating Sets of a Graph

DOI10.1016/J.DISC.2021.112595MaRDI QIDQ6347103arXivFDO

Authors I. Beaton, Jason I. Brown

Publication date 14 August 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.DISC.2021.112595

Mathematics Subject Classification ID

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

arXiv classification

math.CO

Abstract: This papers focuses on the average order of dominating sets of a graph. We find the extremal graphs for the maximum and minimum value over all graphs on $n$ vertices, while for trees we prove that the star minimizes the average order of dominating sets. We prove the average order of dominating sets in graphs without isolated vertices is at most $3n/4$, but provide evidence that the actual upper bound is $2n/3$. Finally, we show that the normalized average, while dense in $[1/2,1]$, tends to $frac12$ for almost all graphs.

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 Q6347103)