8
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – GNiklasch Mar 22 '18 at 8:48
  • $\begingroup$ 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 $\endgroup$ – Dominic van der Zypen Mar 22 '18 at 9:06
  • 3
    $\begingroup$ 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... $\endgroup$ – GNiklasch Mar 22 '18 at 9:39
  • 1
    $\begingroup$ 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$. $\endgroup$ – GNiklasch Mar 22 '18 at 9:41
  • 1
    $\begingroup$ Wouldn't a positive answer to this question provide an essentially trivial polynomial-time algorithm for Graph Isomorphism? $\endgroup$ – Steven Stadnicki Mar 22 '18 at 17:34
7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.