| The enumeration of independent sets in graphs was inaugurated by Prodinger and Tichy [13] who defined, for a graph G, the Fibonacci number of G, denoted f(G), as follows: f(G) is the number of independent vertex sets in G. Prodinger and Tichy determined f(G) for several classes of graphs, including paths, cycles, and 2 x n lattices. Refining the counting, Hopkins and Staton [10] defined, for a graph G and positive interger k: fk(G) is the number of k-element independent vertex sets in G. Hopkins and Staton proposed the program of generating combinatorial identities by computing, for graphs G, both f(G) and f k(G) for all k. This leads to a summation identity: k≥0fk G=fG From their work and the work of Prodinger and Tichy, Hopkins and Staton were able to generate such combinatorial identities for paths, cycles, and 2 x n lattices.;In this dissertation, the program described above will be implemented for three classes of graphs: (1) paths raised to powers; (2) cycles raised to powers; (3) Sunburst graphs. The first two classes of graphs are defined as usual in the graph theory literature. The Sunburst Graphs are defined in this dissertation for the first time. The combinatorial identities arising from the computation of f and fk in these three classes of graphs are as follows: (1) paths: k≥0 n+r-rkk=f n,r (2) cycles: k≥0 n-rkk+r n-1-rkk-1 =ln,r. (3) Sunburst Graphs: k=0n i=0k n-ii+ n-1-ii-1 n-2ik -i =1+2 n+1+2 n. The &phis;(n, r) and lambda(n, r ) are, for fixed r, sequences generalizing the familiar Fibonacci and Lucas sequences.;Also in the dissertation, some new insights on the relationship of Pascal's Triangle and independent vertex sets in paths are developed. Suggestions are made involving directions for future research. |
