A bound on the values of independence polynomials at for -degenerate graphs

An independent set of a graph G is a set of pairwise non-adjacent vertices. Let α ( G ) denote the cardinality of a maximum independent set and f s ( G ) for 0 ≤ s ≤ α ( G ) denote the number of independent sets on s vertices. The independence polynomial I ( G ; x ) = ∑ i = 0 α ( G ) f s ( G ) x s defined first by Gutman and Harary in 1983 has been the focus of considerable research. In 1995, Wingard bounded the function values obtained at − 1 for the independence polynomials for the tree T ; | I ( T ; − 1 ) | ≤ 1 . We generalize Wingard’s result for a much larger class of graphs, k -degenerate graphs, a class which includes all k -trees. Wingard’s result is the case when k = 1 .