On the unimodality of domination polynomials (Q2673493): Difference between revisions

Let \(G\) be a graph of order \(n\). A subset \(S\) of \(V(G)\) is a dominating set of \(G\) if every vertex in \(V(G) \backslash S\) is adjacent to at least one vertex of \(S\). The domination polynomial of \(G\) is the polynomial \(D(G, x) = \sum^n_{i=\gamma(G)} d(G, i)x^i\), where \(d(G, i)\) is the number of dominating sets of \(G\) of size \(i\), and \(\gamma(G)\) is the size of a smallest dominating set of \(G\), called the domination number of \(G\). A finite sequence of real numbers \((a_0, a_1, a_2, \ldots, a_n)\) is said to be unimodal (with mode \(k\)) if \(a_0\le a_1 \le \cdots \le a_{k-1} \le a_k \ge a_{k+1} \ge \cdots \ge a_n\) for some \(k\in \{0,1,2,\ldots,n\}\); and is logarithmically-concave (or simply log-concave) if the inequality \(a^2_k \ge a_{k-1} a_{k+1}\) is valid for every \(k\in \{1,2,\ldots,n-1\}\). Hence, a polynomial \(\sum^n_{k=0} a_kx^k\) is said to be unimodal (or log-concave) if the coefficient sequence \(\{a_k\}\) is unimodal (or log-concave). Motivated by a conjecture by \textit{S. Alikhani} and \textit{Y.-h. Peng} [Opusc. Math. 30, No. 1, 37--51 (2010; Zbl 1220.05084)] which states that the domination polynomial of any graph is unimodal, the authors have shown that the domination polynomial of paths, cycles, and complete multipartite graphs are unimodal. Also, they proved that the domination polynomial of almost every graph is unimodal with mode \(\lceil\frac{n}{2}\rceil\).