Some results on independence polynomials of graphs
by
Bing Wei
University of Mississippi
Coauthors: L. Song and W. Staton

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 f_s(G) for 0 ≤ s ≤ a(G) denote the number of independent sets of s vertices. The independence polynomial I(G;x)=∑_i=0^a(G) f_s(G)x^s defined first by Gutman and Harary has been the focus of considerable research recently. In this talk, we will present some new results on independence polynomials for some classes of graphs. The upper and lower bounds for the coefficients f_s(G) will be discussed. Additionally, we will characterize all instances where our bounds are achieved, and show exactly the independence polynomials of several classes of graphs. Our main theorems generalize several related results known before. This is a joint work with L. Song and W. Staton.

Date received: April 10, 2009