Recurrence relations for graph polynomials on bi-iterative families of graphs

We show that any graph polynomial from a wide class of graph polynomials yields a recurrence relation on an infinite class of families of graphs. The recurrence relations we obtain have coefficients which themselves satisfy linear recurrence relations. We give explicit applications to the Tutte polynomial and the independence polynomial. Furthermore, we get that for any sequence anan satisfying a linear recurrence with constant coefficients, the sub-sequence corresponding to square indices an2an2 and related sub-sequences satisfy recurrences with recurrent coefficients.