Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ we set $N\_0(v) = N(v) = $ $\{w\in V: \{v,w\} \in E\}$ and for $k\in \omega$ let $$N\_{k+1}(v) = N\_k(v) \cup \bigcup\big\{N(z): z\in N\_k(v)\big\}.$$
We define the *neighborhood fingerprint* of $G$ as $F\_G: V\times \omega \to \omega$ defined by $(v,k) \mapsto |N\_k(v)|.$


It is clear that if two graphs $G,H$ are isomorphic, then there is a bijection $\varphi:V(G)\to V(H)$ such that for all $v\in V(H)$ and all $k\in \omega$ we have $F\_G(v,k) = F\_H(\varphi(v), k)$.


Does the converse hold? More precisely, if there is a bijection $\varphi$ as described above, are the graphs $G,H$ isomorphic?



Neighborhood fingerprint of a graph
The answer is no.


Among [Andries E. Brouwer's web pages at TU Eindhoven](http://www.win.tue.nl/~aeb/), the [Cages](http://www.win.tue.nl/~aeb/graphs/cages/cages.html) page lists three non-isomorphic graphs on $70$ vertices (they are $(3,10)$-cages, found by O'Keefe & Wong 1980) with the same distance distribution $1+3+6+12+24+20+4$ around each vertex of each graph.


That is, starting from any vertex $v$, there's one vertex at distance $0$ from it, $3$ immediate neighbor vertices at distance $1$, six at exact distance $2$ (thus nine which are distinct from $v$ and at distance at most $2$ from it, and ten, including $v$ itself - that would give your $F(v,2)$ -, which can be reached from it by traversing at most two edges), and so forth.


Further down the same table, there appear four non-isomorphic $(5,5)$-cages, on $30$ vertices each, all with the same distance distribution $1+5+20+4$ around each vertex.


Elsewhere on those pages, you'll also find corrigenda to the classic reference I had already mentioned in comments: Brouwer-Cohen-Neumaier's *Distance-Regular Graphs*, Springer 1989.


