A note on the values of independence polynomials at -1

Jonathan Cutler, Nathan Kahl

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)2723-2726
Number of pages4
JournalDiscrete Mathematics
Volume339
Issue number11
DOIs
StatePublished - 6 Nov 2016

Keywords

  • Decycling number
  • Independence polynomial

Fingerprint Dive into the research topics of 'A note on the values of independence polynomials at -1'. Together they form a unique fingerprint.

  • Cite this