Almost unimodal and real-rooted graph polynomials (Q2107505)

This paper proves two rather general statements about the unimodality and real-rootedness of polynomials associated with graphs. Let \(\mathcal{A}\) be a graph property and let \(c_i^{\mathcal{A}}(G)\) denote, for a graph \(G\), the number of \(i\)-vertex induced subgraphs of \(G\) that have property \(\mathcal{A}\). The polynomial associated with property \(\mathcal{A}\) is defined as \[ P_{\mathcal{A}}(G;x) = \sum_i c_i^{\mathcal{A}}(G)x^i. \] Recall that a property \(\mathcal{A}\) is called hereditary if it is closed under taking induced subgraphs: in other words, if a graph \(G\) has property \(\mathcal{A}\), then so does every induced subgraph \(H\) of \(G\). The complement \(\mathcal{A}'\) of a property \(\mathcal{A}\) is the property of not satisfying \(\mathcal{A}\). The first main theorem reads as follows: Theorem. If \(\mathcal{A}\) is the complement of a hereditary property, then for almost all graphs, the sequence \(c_i^{\mathcal{A}}(G)\) is unimodal (in other words, the probability that the sequence is unimodal for a random graph \(G(n,1/2)\) tends to \(1\) as \(n \to \infty\)). Second, the following theorem on real-rootedness is shown: Theorem. If \(\mathcal{A}\) is hereditary and satisfied by a graph that is neither complete nor edgeless, then \(P_{\mathcal{A}}(G;x)\) is real-rooted if and only if \(G\) has property \(\mathcal{A}\). These extend results on, e.g., the domination polynomial and the forest polynomial.