Neighborhood fingerprint of a graph

Question

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?

Answer 1

The answer is no.

Among Andries E. Brouwer's web pages at TU Eindhoven, the Cages 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.

Answer 2

Answer. Arguably the simplest infinite set of counterexamples to "Does the converse hold?" are provided by the Möbius ladder's vis-à-vis the prism graphs. Any pair of such graphs (of equal orders) bear stronger similarity to one another than an equal neighborhood fingerprint: all subgraphs induced by balls of radius $r$ are isomorphic (hence the OP's hypothesis holds for such pairs), unless $r\geq\lfloor\frac{\text{number of spokes}}{2}\rfloor$, i.e., unless the balls are large enough to engulf the whole graph and detect the non-isomorphy.

This answers the question.

Remark. While we are at it: the above example can be seen as a reason why the (in)famous Reconstruction Conjecture is so incredible: the condition that all non-trivial balls are isomorphic seems very strong---at first sight perhaps even stronger than the hypothesis in the Reconstruction Conjecture. In particular, the largest balls almost 'look' like the vertex-deleted subgraphs featuring in the Reconstruction Conjecture; and yet, the conclusion that the graphs would have to be isomorphic is false.