| A graph, informally, is a collection of vertices, some pairs of which are joined by edges. An independent set in a graph is a collection of vertices no two of which are joined by an edge. If G is a graph and k is a nonnegative integer, then I denote by "fk( G)" the number of k-vertex independent sets in G. The independence polynomial of G is 0.1 fGx =fkG xk, that is, fG(x) is the generating function for the numbers {fk( G)}. Independence polynomials have been studied extensively in recent mathematical literature. Most of the results are inequalities and asymptotic estimates, but exact formulas have been found for only a few classes of graphs such as paths, cycles, 2 x n lattices and some more trivial classes.;I have studied the independence polynomial for some classes of graphs whose polynomials were not previously known and have found exact formulas in several cases. Among my results are closed formulas for the 2 x n lattices, the cylinders (or ladders), the Mobius ladders, and the combs. For each of these classes of graphs, I use (0.1) to generate a combinatorial identity. I have also considered "matching polynomials," that is, independence polynomials of line graphs, and I have derived a closed expression for the matching polynomials of some generalized combs. Finally, I have investigated the interesting phenomenon of "independence equivalence," the phenomenon of non-isomorphic graphs having identical polynomials. I have found several infinite classes of such pairs of graphs. |
