On the independence polynomials of k-tree related and well-covered graphs.

摘要

Independence Polynomials have been introduced several times, independently and with various names [6, 8, 9], beginning in the early 1980's. Applications have been found in Molecular Chemistry and Statistical Physics. The purposes of this dissertation include the derivation of tight upper and lower bounds for the coefficients of the independence polynomial of a k-tree: n-ks-1 s ≤fsT kn≤ n-k s where Tkn is a k-tree with n vertices and fs is the coefficient of xs in the independence polynomial of Tkn . All instances of equality at the upper and lower bounds are determined. This result generalizes a theorem of Wingard [21] corresponding to k = 1.;A second focus of this dissertation is the exact determination of the independence polynomials in several classes of k-trees, including (k, n)-paths, (k, n)-stars, and ( k, n)-spirals, and in some graphs which are closely related to k-trees. These include (k, n)-cycles and ( k, n)-wheels.;A third focus is the determination of the independence polynomial in a certain class of well-covered graphs. These graphs are described by a construction in Chapter 4 and their independence polynomials are computed using a very general theorem. In cases where the polynomial can be determined in closed form and its coefficients determined separately, the independence polynomial is used to generate some new combinatorial identities.;Finally, the independence structure of the line graph of a 2 x n lattice is considered. While the exact determination of the polynomial remains an open question, the fibonacci number of this graph, that is, the sum of the coefficients of its polynomial, is determined precisely for all n.;At the end of this dissertation, some further related research problems are proposed.