The Cyclomatic Number of a Graph and its Independence Polynomial at -1

摘要

If by s_k is denoted the number of independent sets of cardinality k in a graph G, then I(G; x) = s_0 + s_1x +...+ s_αx ~α is the independence polynomial of G (Gutman and Harary in Utilitas Mathematica 24:97-106, 1983), where α = α(G) is the size of a maximum independent set. The inequality {pipe}I (G; -1){pipe} ≤ 2~(ν(G)), where ν(G) is the cyclomatic number of G, is due to (Engstr?m in Eur. J. Comb. 30:429-438, 2009) and (Levit and Mandrescu in Discret. Math. 311:1204-1206, 2011). For ν(G) ≤ 1 it means that I(G; -1) ∈ {-2, -1, 0, 1, 2} In this paper we prove that if G is a unicyclic well-covered graph different from C_3, then I(G; -1) ∈ {-1, 0, 1}, while if G is a connected well-covered graph of girth ≥ 6, non-isomorphic to C_7 or K_2 (e. g., every well-covered tree ≠ K_2), then I (G; -1) = 0. Further, we demonstrate that the bounds {-2~(ν(G)), 2~(ν(G))} are sharp for I (G; -1), and investigate other values of I (G; -1) belonging to the interval [-2~(ν(G)), 2~(ν(G))].