The monotonicity sandwich conjecture for average dominating-set order
Let be a nonempty graph. For a vertex and an edge , write and for the graphs obtained by deleting and , respectively. The monotonicity sandwich conjecture. There exist a vertex and an edge such that
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 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
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.