The independence polynomial I ( G ; x ) of a graph G is I ( G ; x ) = ź k = 0 α ( 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 ź V ( G ) such that G - S is acyclic. Engstrom proved that the independence polynomial satisfies | I ( G ; - 1 ) | ź 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 | ź 2 k , there is a connected graph G with ź ( G ) = k and I ( G ; - 1 ) = q . In this note, we prove this conjecture.
['Jonathan Cutler', 'Nathan Kahl']
A note on the values of independence polynomials at - 1