  We give a method of generating strongly polynomial sequences of graphs, i.e.,
sequences $(H_{\mathbf{k}})$ indexed by a multivariate parameter
$\mathbf{k}=(k_1,\ldots, k_h)$ such that, for each fixed graph $G$, there is a
multivariate polynomial $p(G;x_1,\ldots, x_h)$ such that the number of
homomorphisms from $G$ to $H_{\mathbf{k}}$ is given by the evaluation
$p(G;k_1,\ldots, k_h)$. A classical example is the sequence $(K_k)$ of complete
graphs, for which ${\rm hom}(G,K_k)=P(G;k)$ is the evaluation of the chromatic
polynomial at $k$. Our construction produces a large family of graph
polynomials that includes the Tutte polynomial, the Averbouch-Godlin-Makowsky
polynomial and the Tittmann-Averbouch-Makowsky polynomial. We also introduce a
new graph parameter, the {\em branching core size} of a simple graph, related
to how many involutive automorphisms with fixed points it has. We prove that a
countable family of graphs of bounded branching core size (which in particular
implies bounded tree-depth) is always contained in a finite union of strongly
polynomial sequences.
