# Sufficient condition for simple graph isomorphism?

Say I have two simple graphs, $A$ and $B$

• In $A$, I know:

• one node has 3 nodes at distance of 1, 4 nodes at distance 2, etc.
• one node has 4 nodes at distance of 1, 1 nodes at distance 2, etc.
• etc.
• In $B$, I know:

• one node has 3 nodes at distance of 1, 4 nodes at distance 2, etc.
• one node has 4 nodes at distance of 1, 1 nodes at distance 2, etc.
• etc.

Can I derive that graph $A$ and $B$ are isomorphic to each other? Or is there a counter-example where two graphs look the same from this distance point of view, but are not isomorphic?

It is a necessary condition, so if these simple graphs are isomorphic, they will share these distances. I am wondering if this is a sufficient condition as well.

• I have indeed corrected the title and added a clarification with what is meant by geodesic distance. – 317070 Mar 5 '15 at 16:39
• The complexity of graph isomorphism is a famous open problem in computer science and if your condition were sufficient, that would immediately give a simple polynomial-time algorithm. It's very unlikely that everybody would have missed such a simple algorithm, if one existed. – David Richerby Mar 5 '15 at 20:47
• DRs comment does not formalize this single instance to something more general. a more general way/ algorithm would seem to involve computing a "distance matrix" for the graph. – vzn Mar 6 '15 at 5:41

There are two non-isomorphic graphs with 16 vertices in which each vertex has 6 neighbors and 9 vertices at distance 2: the Shrikhande graph and the $4\times 4$ rook's graph.