On the unimodality of independence polynomials of some graphs (Q607359)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the unimodality of independence polynomials of some graphs |
scientific article |
Statements
On the unimodality of independence polynomials of some graphs (English)
0 references
22 November 2010
0 references
Let \(G\) be a graph and let \(i_k(G)\) be the number of independent sets of \(G\) of size \(k\). Set \(i_0(G) = 1\). Then \(\sum _{k=0} ^{\alpha (G)} i_k(G)x^k\) is called the independence polynomial of \(G\), where \(\alpha (G)\) is the independence number of \(G\). Further, a sequence of numbers \(a_0, a_1,\dots,a_n\) is called unimodal if there exists an \(m\) such that \(a_0\leq a_1\leq \dots \leq a_m \geq a_{m+1}\geq \dots \geq a_n\); and it is called log-concave if \(a_{k}^2\geq a_{k-1}a_{k+1}\) for all \(1\leq k\leq n-1\). A polynomial is unimodal (log-concave) if the sequence of its coefficients has the property. In the paper the unimodality, log-concavity, and reality of zeros of the independence polynomial for some special classes of graphs is studied.
0 references
independence polynomial of a graph
0 references
unimodality
0 references
log-concavity
0 references
0 references