The monotonicity sandwich conjecture for average dominating-set order

From papers

Let GG be a nonempty graph. For a vertex vv and an edge ee, write GvG-v and GeG-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(Gv)<avd(G)<avd(Ge).\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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.