### Abstract

The independence polynomial I(G;x) of a graph G is I(G;x)=∑_{k=0} ^{α}(G)s_{k}x^{k}, 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|≤2^{k}, there is a connected graph G with φ(G)=k and I(G;-1)=q. In this note, we prove this conjecture.

Original language | English |
---|---|

Pages (from-to) | 2723-2726 |

Number of pages | 4 |

Journal | Discrete Mathematics |

Volume | 339 |

Issue number | 11 |

DOIs | |

State | Published - 6 Nov 2016 |

### Fingerprint

### Keywords

- Decycling number
- Independence polynomial

### Cite this

*Discrete Mathematics*,

*339*(11), 2723-2726. https://doi.org/10.1016/j.disc.2016.05.019

}

*Discrete Mathematics*, vol. 339, no. 11, pp. 2723-2726. https://doi.org/10.1016/j.disc.2016.05.019

**A note on the values of independence polynomials at -1.** / Cutler, Jonathan; Kahl, Nathan.

Research output: Contribution to journal › Article › Research › peer-review

TY - JOUR

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

AU - Cutler, Jonathan

AU - Kahl, Nathan

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

VL - 339

SP - 2723

EP - 2726

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 11

ER -