4
$\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.

Improve this question
$\endgroup$
3
  • $\begingroup$ I have indeed corrected the title and added a clarification with what is meant by geodesic distance. $\endgroup$
    – 317070
    Mar 5, 2015 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, 2015 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, 2015 at 5:41

1 Answer 1

Reset to default
10
$\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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ See also strongly regular graphs, which both of these happen to be. $\endgroup$
    – Pål GD
    Mar 6, 2015 at 7:14
  • $\begingroup$ Is the OP's condition sufficient for graphs with less than 16 vertices, then? $\endgroup$
    – BeeOnRope
    Jul 13, 2016 at 23:49
  • $\begingroup$ @BeeOnRope I don't find this a terribly interesting question. $\endgroup$
    – Yuval Filmus
    Jul 13, 2016 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, 2016 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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