Independence polynomials of k-tree related graphs

An independent set of a graph G is a set of pairwise non-adjacent vertices Let a (G) denote the cardinality of a maximum independent set and integral s(G)) for 0 <= s <= an denote the number of independent sets of s vertices. The independence polynomial I(G: x) = Sigma(alpha(G))(1=0) integral s(G)x(5) defined first by Gutman and Harary has been the focus of considerable research recently Wingard bounded the coefficients integral s(T)(T) for trees T with n vertices. (n+1-s/s,1) <= integral s(T) <= (n-1/s) 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. (C) 2010 Elsevier B.V All rights reserved