Independence polynomials of k-tree related graphs

An independent set of a graph GG is a set of pairwise non-adjacent vertices. Let α(G)α(G) denote the cardinality of a maximum independent set and fs(G)fs(G) for 0≤s≤α(G)0≤s≤α(G) denote the number of independent sets of ss vertices. The independence polynomial I(G;x)=∑i=0α(G)fs(G)xs defined first by Gutman and Harary has been the focus of considerable research recently. Wingard bounded the coefficients fs(T)fs(T) for trees TT with nn vertices: (n+1−ss)≤fs(T)≤(n−1s) for s≥2s≥2. We generalize this result to bounds for a very large class of graphs, maximal kk-degenerate graphs, a class which includes all kk-trees. Additionally, we characterize all instances where our bounds are achieved, and determine exactly the independence polynomials of several classes of kk-tree related graphs. Our main theorems generalize several related results known before.