TY - JOUR
T1 - A note on the values of independence polynomials at -1
AU - Cutler, Jonathan
AU - Kahl, Nathan
N1 - Publisher Copyright:
© 2016 Elsevier B.V. All rights reserved.
PY - 2016/11/6
Y1 - 2016/11/6
N2 - The independence polynomial I(G;x) of a graph G is I(G;x)=∑k=0α(G)skxk, where sk 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 SV(G) such that G-S is acyclic. Engström 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|≤2k, there is a connected graph G with φ(G)=k and I(G;-1)=q. In this note, we prove this conjecture.
AB - The independence polynomial I(G;x) of a graph G is I(G;x)=∑k=0α(G)skxk, where sk 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 SV(G) such that G-S is acyclic. Engström 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|≤2k, there is a connected graph G with φ(G)=k and I(G;-1)=q. In this note, we prove this conjecture.
KW - Decycling number
KW - Independence polynomial
UR - http://www.scopus.com/inward/record.url?scp=84974589010&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2016.05.019
DO - 10.1016/j.disc.2016.05.019
M3 - Article
AN - SCOPUS:84974589010
SN - 0012-365X
VL - 339
SP - 2723
EP - 2726
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 11
ER -