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\geq0}a_ix^i$ and $I(G_2;x)=\sum_{i\geq0}b_ix^i$, where $I(G_2;x)$ is log-concave. Then we prove

(i) if $I(G_1;x)$ is log-concave and $(a^2_i-a_{i-1}a_{i+1})b^2_1\geq a_ia_{i-1}b_2$ for
all $1\leq i \leq \alpha(G_1)$, then $I(G_1[G_2];x)$ is log-concave;
(ii) if $a_{i-1}\leq b_1a_i$ for $1\leq i\leq \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\u{a}.