# On a GI complete class

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.

• 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? Commented Nov 25, 2017 at 12:31
• Well, for any graph you can add 1 vertex connected to everything and it will belong to this class. Commented Nov 25, 2017 at 13:03
• ok did not think carefully. Commented Nov 25, 2017 at 13:04
• Well I enjoyed figuring out this question Commented Nov 25, 2017 at 13:15