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?

Distance-Regular Graphsmight contain explicit examples of non-isomorphic DRGs with the same intersection arrays (a stronger condition than yours), but my copy of the book is buried in a box somewhere, and a quick trawl for online tables only found examples for existence and uniqueness - where the uniqueness results tend to require elaborate proofs... $\endgroup$1more comment