A note on the values of independence polynomials at −1−1

The independence polynomial  I(G;x)I(G;x) of a graph GG is I(G;x)=∑k=0α(G)skxk, where sksk is the number of independent sets in GG of size kk. The decycling number   of a graph GG, denoted ϕ(G)ϕ(G), is the minimum size of a set S⊆V(G)S⊆V(G) such that G−SG−S is acyclic. Engström proved that the independence polynomial satisfies |I(G;−1)|≤2ϕ(G)|I(G;−1)|≤2ϕ(G) for any graph GG, 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 kk and integer qq with |q|≤2k|q|≤2k, there is a connected graph GG with ϕ(G)=kϕ(G)=k and I(G;−1)=qI(G;−1)=q. In this note, we prove this conjecture.