Say I have two simple graphs, A and B In A, I know: one node has 3 nodes at dist

Question

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.

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.