The monotonicity sandwich conjecture for average dominating-set order
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.