Unimodality of the independence polynomials of some composite graphs

Abstract

Let $I(G;x)$ denote the independence polynomial of a graph $G$. In this paper we study the unimodality properties of $I(G;x)$ for some composite graphs $G$. Given two graphs $G_1$ and $G_2$, let $G_1[G_2]$ denote the lexicographic product of $G_1$ and $G_2$. Assume $I(G_1;x)={\sum }_{i\ge 0}{a}_i{x}^i$ and $I(G_2;x)={\sum }_{i\ge 0}{b}_i{x}^i$, where $I(G_2;x)$ is log-concave. Then we prove (i) if $I(G_1;x)$ is log-concave and $(a_i^2-a_{i-1}{a}_{i+1})b_1^2\ge a_i{a}_{i-1}{b}_2$ for all $1\le i\le \alpha (G_1)$, then $I(G_1[G_2];x)$ is log-concave; (ii) if $a_{i-1}\le b_1{a}_i$ for $1\le i\le \alpha (G_1)$, then $I(G_1[G_2];x)$ is unimodal. In particular, if $a_i$ is increasing in $i$, then $I(G_1[G_2];x)$ is unimodal. We also give two sufficient conditions when the independence polynomial of a complete multipartite graph is unimodal or log-concave. Finally, for every odd positive integer $\alpha >3$, we find a connected graph $G$ not a tree, such that $\alpha (G)=\alpha$, and $I(G;x)$ is symmetric and has only real zeros. This answers a problem of Mandrescu and Mirică.

It will appear in Filomat