Beaton–Brown average dominating-set order conjecture

About 5 years old · traced to

Let GG be a graph with n≥2n\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.

References

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.