A note on the values of independence polynomials at $-1$

Abstract

The independence polynomial $I(G;x)$ of a graph $G$ is $I(G;x)={\sum }_{k=1}^{\alpha (G)}{s}_k{x}^k$, where $s_k$ is the number of independent sets in $G$ of size $k$. The decycling number of a graph $G$, denoted $\varphi (G)$, is the minimum size of a set $S\subseteq V(G)$ such that $G-S$ is acyclic. Engström proved that the independence polynomial satisfies $|I(G;-1)|\le 2^{\varphi (G)}$ for any graph $G$, and this bound is best possible. Levit and Mandrescu provided an elementary proof of the bound, and in addition conjectured that for every positive integer $k$ and integer $q$ with $|q|\le 2^k$, there is a connected graph $G$ with $\varphi (G)=k$ and $I(G;-1)=q$. In this note, we prove this conjecture.