Unimodality conjecture for dominating-set sequences of finite graphs

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 0≤j≤n0\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 0≤m≤n0\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.

References

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).

Progress summary

Never refreshed

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.