On graph invariants given by linear recurrence relations

A sequence of graphs G_n is iteratively constructible if it can be built from an initial labeled graph by means of a repeated fixed succession of elementary operations involving addition of vertices and edges, deletion of edges, and relabelings. Let G_n ...

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. ...

For a graph G, a graph recurrence sequence x₀, x₁, x₂,... of vectors is defined by the recurrence x_t+1 = Ax_t, t = 0, 1,...., where A is the adjacency matrix of G and x₀ is an initial vector. Each vector in this sequence can be thought of as a vertex ...