patternModerate
Sufficient condition for simple graph isomorphism?
Viewed 0 times
simpleconditiongraphisomorphismforsufficient
Problem
Say I have two simple graphs, $A$ and $B$
-
In $A$, I know:
-
In $B$, I know:
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.
-
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.
Solution
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.
Context
StackExchange Computer Science Q#40094, answer score: 10
Revisions (0)
No revisions yet.