Unimodality conjecture for dominating-set sequences of finite graphs

From papers

Let GG be a finite undirected graph on nn 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 0jn0\leq j\leq n, let dj(G)d_j(G) be the number of dominating sets of GG with cardinality jj. Unimodality conjecture. The sequence d0(G),,dn(G)d_0(G),\ldots,d_n(G) is unimodal: there exists some 0mn0\leq m\leq n such that

d0(G)d1(G)dm(G)dm+1(G)dn(G).d_0(G)\leq d_1(G)\leq\cdots\leq d_m(G)\geq d_{m+1}(G)\geq\cdots\geq d_n(G).

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

No solutions have been posted yet.