# Neighborhood fingerprint of a graph

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?

• Do you just want "isomorphic" in the converse, or that the given $\varphi$ itself provide an isomorphism? In the latter case, the answer is no (there are distance-regular graphs - where, taking $H=G$, every permutation of the vertices is such a $\varphi$ - which aren't even vertex-transitive). – GNiklasch Mar 22 '18 at 8:48
• Thanks for your question of clarification - I don't want the given $\varphi$ itself necessarily to be an isomorphism. I will clarify this in the problem description – Dominic van der Zypen Mar 22 '18 at 9:06
• Thank you for clarifying! I suspect the answer is still no, and that the extensive tables in Brouwer-Cohen-Neumaier Distance-Regular Graphs might 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... – GNiklasch Mar 22 '18 at 9:39
• In any case, questions of this nature are usually studied in terms of distance, and of the sets $G_k(v)$ of vertices at exact distance $k$ from a given vertex $v$. – GNiklasch Mar 22 '18 at 9:41
• Wouldn't a positive answer to this question provide an essentially trivial polynomial-time algorithm for Graph Isomorphism? – Steven Stadnicki Mar 22 '18 at 17:34

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. 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.