https://en.wikipedia.org/wiki/Graph_isomorphism_problem#GI-complete_classes_of_graphs says deciding diameter $2$ radius $1$ graph isomorphism is $GI$ complete.

Is it possible only the diameter $2$ radius $1$ bipartite graph isomorphism (there is only one structure for this I can think of - vertices of color $1$ in first and third column with vertices of color $2$ in second column and first and third column having no direct edges) is $GI$ complete?


No, that's not $\mathrm{GI}$-complete unless $\mathrm{GI}\in\textsf{P}$. Indeed, isomorphism of such graphs can be checked in polynomial time.

First, note that a bipartite graph is triangle-free.

Second, we may assume our graphs are connected, since otherwise we just consider isomorphism connected-component by connected-component, with an at most polynomial slowdown.

So we just have to determine isomorphism between two triangle-free, diameter 2, radius 1, connected graphs. These are all star-shaped.

Thus by merely checking degrees of vertices, we determine whether isomorphism holds.

  • $\begingroup$ so the class of diameter $2$ and radius $1$ graphs does not seem very rich (sounds similar to star-shaped in some sense). How is this $GI$-complete? $\endgroup$
    – Turbo
    Nov 25 '17 at 12:31
  • 1
    $\begingroup$ Well, for any graph you can add 1 vertex connected to everything and it will belong to this class. $\endgroup$ Nov 25 '17 at 13:03
  • $\begingroup$ ok did not think carefully. $\endgroup$
    – Turbo
    Nov 25 '17 at 13:04
  • 1
    $\begingroup$ Well I enjoyed figuring out this question $\endgroup$ Nov 25 '17 at 13:15

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.