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?


1 Answer 1


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
    Commented Nov 25, 2017 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$ Commented Nov 25, 2017 at 13:03
  • $\begingroup$ ok did not think carefully. $\endgroup$
    – Turbo
    Commented Nov 25, 2017 at 13:04
  • 1
    $\begingroup$ Well I enjoyed figuring out this question $\endgroup$ Commented Nov 25, 2017 at 13:15

Your Answer

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

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