Independence polynomials of k-tree related graphs

AbstractAn 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 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) for trees T with n vertices: (n+1−ss)≤fs(T)≤(n−1s) 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