Beaton–Brown average dominating-set order conjecture

Let GG be a graph with n2n\geq 2 vertices, and let avd(G)\operatorname{avd}(G) denote its average order of dominating sets. If GG has no isolated vertices, then Beaton–Brown's conjecture.

avd(G)2n3.\operatorname{avd}(G)\leq \frac{2n}{3}.

The conjecture sharpens the previously known upper bound 3n/43n/4 for graphs without isolated vertices. The supplied status evidence indicates that the result is proved in this paper.

Sources & referencesView supporting material

Primary source

Iain Beaton and Ben Cameron, “A Tight Upper Bound on the Average Order of Dominating Sets of a Graph”, arXiv:2208.10475 (2022).

Additional references

2 papers in this index state this conjecture (2021–2022). The statement above is taken from the most recent of them; the others are arXiv:2104.00600.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.