A note on the values of independence polynomials at-1

作者：Cutler Jonathan; Kahl Nathan^*

来源：Discrete Mathematics, 2016, 339(11): 2723-2726.

DOI：10.1016/j.disc.2016.05.019

• Independence polynomial
• Decycling number

The independence polynomial I(G; x) of a graph G is I(G; x) = Sigma(alpha(G))(k=0) 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 phi(G), is the minimum size of a set S subset of V(G) such that G - S is acyclic. Engstrom proved that the independence polynomial satisfies vertical bar I(G; -1)vertical bar <= 2(phi(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 vertical bar q vertical bar <= 2(k), there is a connected graph G with phi(G) = k and I (G; -1 = q. In this note, we prove this conjecture.

• 出版日期2016-11-6