3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have indeed corrected the title and added a clarification with what is meant by geodesic distance. $\endgroup$ – 317070 Mar 5 '15 at 16:39
  • 3
    $\begingroup$ 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. $\endgroup$ – David Richerby Mar 5 '15 at 20:47
  • $\begingroup$ 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. $\endgroup$ – vzn Mar 6 '15 at 5:41
9
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ See also strongly regular graphs, which both of these happen to be. $\endgroup$ – Pål GD Mar 6 '15 at 7:14
  • $\begingroup$ Is the OP's condition sufficient for graphs with less than 16 vertices, then? $\endgroup$ – BeeOnRope Jul 13 '16 at 23:49
  • $\begingroup$ @BeeOnRope I don't find this a terribly interesting question. $\endgroup$ – Yuval Filmus Jul 13 '16 at 23:51
  • $\begingroup$ Sorry (I guess?), but It is interesting for me. For example, I want to quickly compute isomorphism groups for graphs for limited n, generally n < 15. So such a shortcut would be useful. In any case, the strength of stackexchange is that it only takes one person to find something interesting to reply! $\endgroup$ – BeeOnRope Jul 13 '16 at 23:53

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.