| Abstract: | 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 fs(G) for 0≤s≤α(G) denote the number of independent sets of s vertices. The independence polynomial  defined first by Gutman and Harary has been the focus of considerable research recently. Wingard bounded the coefficients fs(T) for trees T with n vertices:  for s≥2. We generalize this result to bounds for a very large class of graphs, maximal k-degenerate graphs, a class which includes all k-trees. Additionally, we characterize all instances where our bounds are achieved, and determine exactly the independence polynomials of several classes of k-tree related graphs. Our main theorems generalize several related results known before. |
