  A strongly polynomial sequence of graphs $(G_n)$ is a sequence
$(G_n)_{n\in\mathbb{N}}$ of finite graphs such that, for every graph $F$, the
number of homomorphisms from $F$ to $G_n$ is a fixed polynomial function of $n$
(depending on $F$). For example, $(K_n)$ is strongly polynomial since the
number of homomorphisms from $F$ to $K_n$ is the chromatic polynomial of $F$
evaluated at $n$. In earlier work of de la Harpe and Jaeger, and more recently
of Averbouch, Garijo, Godlin, Goodall, Makowsky, Ne\v{s}et\v{r}il, Tittmann,
Zilber and others, various examples of strongly polynomial sequences and
constructions for families of such sequences have been found.
  We give a new model-theoretic method of constructing strongly polynomial
sequences of graphs that uses interpretation schemes of graphs in more general
relational structures. This surprisingly easy yet general method encompasses
all previous constructions and produces many more. We conjecture that, under
mild assumptions, all strongly polynomial sequences of graphs can be produced
by the general method of quantifier-free interpretation of graphs in certain
basic relational structures (essentially disjoint unions of transitive
tournaments with added unary relations). We verify this conjecture for strongly
polynomial sequences of graphs with uniformly bounded degree.
