ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.