Properties and applications of the Fibonacci polynomial of a graph

The enumeration of independent sets in a graph has been an important combinatorial topic for some time. In a 1982 paper, Prodinger and Tichy defined the Fibonacci number of a graph to be the total number of independent sets in a graph. Hopkins and Staton refined this notion in 1984 by defining the Fibonacci polynomial of a graph.;In this dissertation, two formulas, the vertex and edge reduction formulas, are derived for use in finding the Fibonacci polynomial of a graph. Formulas for the Fibonacci polynomial of complete graphs, complete bipartite graphs, independent sets, stars, paths, cycles, and wheels are presented, and formulas are also derived for disjoint union, join, and composition of graphs. Trees are studied in detail, and best possible bounds are derived for the coefficients of the Fibonacci polynomial of a tree. A characterization is proved for forests which are balanced, that is, for forests which have the same number of even-and odd-sized independent sets.;Two open questions from the Prodinger and Tichy paper are addressed. A generating function is derived which provides the Fibonacci number for the generalized Petersen graph. Also, generating functions are determined for 3 x n and 4 x n lattices which give the Fibonacci polynomials for these lattices. This provides a partial solution for this question of the Fibonacci number of m x n lattices even though a general formula for the Cartesian product of two graphs is unknown.;Also in this dissertation, second order linear homogeneous recursion relations are considered, and relationships between the integer coefficients are investigated for those recursions which have a graphical representation.;Rook polynomials are shown to be Fibonacci polynomials. It is proved that chessboard graphs are line graphs of bipartite graphs, and those graphs which are chessboard graphs are characterized in terms of a small set of forbidden induced subgraphs. The concept of a chessboard is expanded to higher dimensions, and a set of graphs is presented which are forbidden as induced subgraphs of higher dimensional chessboards.;The average size of an independent set is determined for those classes of graphs for which a polynomial in closed form exists.