The Average Order of Dominating Sets of a Graph

This talk 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 1/2 for almost all graphs.

The Atlantic Graph Theory Seminar series will take place every Wednesday from 3:30-4:30 ADT online via zoom. The talks, provided by researchers, postdocs and graduate students, will be on a variety of current topics in graph theory. If you would like to give a talk or attend, please email one of the organizers (Jason Brown and Danielle Cox).