  Some well-known results of Prodinger and Tichy are that the number of
independent sets in the $n$-vertex path graph is $F_{n+2}$, and that the number
of independent sets in the $n$-vertex cycle graph is $L_n$. We generalize these
results by introducing new classes of graphs whose independent set structures
encode the Lucas sequences of both the first and second kind. We then use this
class of graphs to provide new combinatorial interpretations of the terms of
Dickson polynomials of the first and second kind.
