A note on the values of independence polynomials at -1

2014/10/28 by Jonathan Cutler, Cutler, Jonathan, Nathan Kahl +1
Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO

paper · pdf · doi:10.48550/arxiv.1410.7726

arxiv created 2014/10/28 · openalex publication_date 2014/10/28 · arxiv updated 2014/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The independence polynomial I(G;x) of a graph G is I(G;x)=∑_k=1^α(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. 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.

Related

• A note on the alternating number of independent sets in a graph
• A Simple Proof of an Inequality Connecting the Alternating Number of Independent Sets and the Decycling Number
• The independence polynomial of a graph at -1
• On The Roots of Independence Polynomial: Quantifying The Gap
• On the Unimodality of Independence Polynomials of Very Well-Covered Graphs