A Simple Proof of an Inequality Connecting the Alternating Number of Independent Sets and the Decycling Number

2009/05/21 by Vadim E. Levit, Levit, Vadim E., Eugen Mândrescu +2 · 1 citation
Computer Science · Mathematics · #05A20 (Primary) #05C69 #52B05 #57M15 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #cs.DM #math.CO #msc:05A20 #msc:05C69 #msc:52B05 #msc:57M15

paper · pdf · doi:10.48550/arxiv.0905.3487

4 pages

arxiv created 2009/05/21 · openalex publication_date 2009/05/21 · arxiv updated 2011/01/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

If alpha=alpha(G) is the maximum size of an independent set and s_k equals the number of stable sets of cardinality k in graph G, then I(G;x)=s₀+s₁x+...+s_alphax^alpha is the independence polynomial of G. In this paper we provide an elementary proof of the inequality claiming that the absolute value of I(G;-1) is not greater than 2^phi(G), for every graph G, where phi(G) is its decycling number.

Citations

• The independence polynomial of a graph at -1

Cited by

• On the independent set polynomial of graphs and claw-free graphs

Related

• A note on the values of independence polynomials at -1
• The independence polynomial of a graph at -1
• A note on the alternating number of independent sets in a graph
• On The Roots of Independence Polynomial: Quantifying The Gap
• Cardinalities of the total number of independent sets