Given $q \in \mathbb{N}$, let $B_q$ be a sequence of all (non isomorphic) connected graphs with at most $q$ vertices. Now for a given connected graph $G$, lets define signature of $G$ ($sig_q(G)$) as an integer-valued vector of length $|B_q|$ such that $sig_q(G)[i]=$ number of occurrences of graph $B_q[i]$ in $G$.

The question is: how large $q$ do we have to take so that any graph on $n$ vertices is uniquely determined by $sig_q(G)$?

I thought that it would be sufficient to take $q$ close to the diameter of $G$, but the following counter-example shows two graphs with diameter 4 that have the same $sig_4$ but are not isomorphic.

[Two non-isomorphic graphs with the same signature][1]


  [1]: https://i.sstatic.net/Wy6o2.png