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

The independence polynomial $I(G;x)$ of a graph $G$ is $I(G;x)=\sum_{k=1}^{α(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 $ϕ(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)| \leq 2^{ϕ(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|\leq 2^k$, there is a connected graph $G$ with $ϕ(G)=k$ and $I(G;-1)=q$. In this note, we prove this conjecture.

No reviews yet.

No comments yet.