The monotonicity sandwich conjecture for average dominating-set order

About 6 years old · traced to

Let GG be a nonempty graph. For a vertex vv and an edge ee, write G−vG-v and G−eG-e for the graphs obtained by deleting vv and ee, respectively. The monotonicity sandwich conjecture. There exist a vertex vv and an edge ee such that

avd⁡(G−v)<avd⁡(G)<avd⁡(G−e).\operatorname{avd}(G-v)<\operatorname{avd}(G)<\operatorname{avd}(G-e).

Although deleting a vertex or edge always decreases the number of dominating sets, it need not make the average order of a dominating set monotone in either direction. The conjecture is reported to hold for all graphs on at most 77 vertices; its validity for all nonempty graphs remains open.

References

Primary source

Iain Beaton and Jason I. Brown, “The Average Order of Dominating Sets of a Graph”, arXiv:2008.06531 (2020).

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.