The monotonicity sandwich conjecture for average dominating-set order
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.
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
Sign in to submit a solution.
No solutions have been posted yet.