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

<p>First, note that a bipartite graph is <strong>triangle-free</strong>. </p>

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

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

<p>Thus by merely checking degrees of vertices, we determine whether isomorphism holds.</p>

CC BY-SA 3.0
2017-11-25T13:03:12.127Z
Well, for any graph you can add 1 vertex connected to everything and it will belong to this class.
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2017-11-25T13:04:45.513Z
ok did not think carefully.
Turbo
CC BY-SA 3.0
2017-11-25T13:15:42.127Z
Well I enjoyed figuring out this question
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2017-11-25T12:31:18.510Z
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?
Turbo
CC BY-SA 3.0
2017-11-25T01:59:22.633Z
2017-11-25T02:31:02.603Z
2017-11-25T02:31:02.603Z
Bjørn Kjos-Hanssen
<p><a href="https://en.wikipedia.org/wiki/Graph_isomorphism_problem#GI-complete_classes_of_graphs" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Graph_isomorphism_problem#GI-complete_classes_of_graphs</a> says deciding diameter $2$ radius $1$ graph isomorphism is $GI$ complete.</p>

<p>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?</p>

<graph-isomorphism>
On a GI complete class
Turbo
# On a GI complete class

(Asked by: username_0 on 2017-11-25)

<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?

**Tags:** graph-isomorphism

---

## 1 answers

### Answer by username_1 on 2017-11-25. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: Well, for any graph you can add 1 vertex connected to everything and it will belong to this class.  
> **username_0**: ok did not think carefully.  
> **username_1**: Well I enjoyed figuring out this question  

---

