Unimodality conjecture for dominating-set sequences of finite graphs
Unimodality conjecture for dominating-set sequences of finite graphs
Let be a finite undirected graph on vertices. A dominating set is a set of vertices such that every vertex is either in the set or adjacent to a vertex in the set. For , let be the number of dominating sets of with cardinality . Unimodality conjecture. The sequence is unimodal: there exists some such that
The conjecture concerns the shape of dominating-set enumerators, while this paper gives examples showing that dominating-set sequences need not be log-concave. Since log-concavity implies unimodality under the relevant endpoint conditions, disproving log-concavity does not by itself disprove this conjecture; the supplied text gives no resolution status for the unimodality claim.
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
Alina Du, Steven Heilman and Greta Panova, “Trees and Graphs with Non Log-concave Dominating Set Sequence via AI Tools”, arXiv:2605.02193 (2026).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.