<p>Isn't this graph just a collection of cycles? So we only need to compare that all the lengths in the two graphs match (which can be done by sorting the lengths).</p>

CC BY-SA 3.0
2015-10-07T20:28:38.060Z
You mean lengths of all cycles?
Omar Shehab
CC BY-SA 3.0
2015-10-07T21:11:01.597Z
I am not sure what definition of 'cycle graph' he has used here. According the the definition in Wikipedia (https://en.wikipedia.org/wiki/Cycle_graph), a cycle graph can have only one cycle. In that case, there cannot be any cycle graph for the permutation $(1 2)(3 4)$, right?
Omar Shehab
CC BY-SA 3.0
2015-10-08T02:35:43.953Z
It's clearly a collection of disjoint cycles, being a 2-regular graph. And Igor's algorithm obviously works.
Sasho Nikolov
CC BY-SA 3.0
2015-10-07T20:10:44.210Z
2015-10-07T20:10:44.210Z
Igor Shinkar
<p>This question is supplementary to the question asked <a href="https://math.stackexchange.com/questions/1469024/which-graphs-do-have-invertible-adjacency-matrices">here</a>.</p>

<p>One of the answers give a class of graphs for which the adjacency matrices are invertible which is defined as follows.</p>

<blockquote>
  <p>Given a permutation $\pi$ of a finite set $V$, form its cycle graph
  $G$ as follows: the vertex set is $V$ and the edges are pairs $(v,w)$
  for which $\pi(v)=w$. (This is a simple directed graph.) The adjacency
  matrix will in fact be the permutation matrix corresponding to $\pi$,
  which is invertible.</p>
</blockquote>

<p>Let's consider a class of graph isomorphism problems where it is promised that both of the input graphs will be from the class defined above.</p>

<p>Can the graph isomorphism problems from this class be solved efficiently?</p>

CC BY-SA 3.0
2015-10-08T04:11:46.960Z
Note that if you work with the larger class of all graphs whose adjacency matrices are invertible, I believe the problem becomes GI-complete. (Namely, given any graph, add a new neighbor of degree 1 to each vertex. The resulting graph has invertible adjacency matrix.)
Joshua Grochow
CC BY-SA 3.0
2015-10-08T04:45:20.727Z
@JoshuaGrochow, interesting. Could you please point me to a paper/resource on it? I would like to know more.
Omar Shehab
CC BY-SA 3.0
2015-10-08T18:17:02.823Z
I have asked the question here. http://math.stackexchange.com/questions/1470764/class-of-all-graphs-with-invertible-adjacency-matrices
Omar Shehab
CC BY-SA 3.0
2015-10-08T20:50:08.707Z
I do not know a paper on this particular question. Is there something basic you didn't understand about my comment? If you understand the basics (e.g. what GI-complete means), then I'd treat the rest of my comment as a good exercise.
Joshua Grochow
<graph-theory><linear-algebra><matrices><graph-isomorphism><permutations>
Graph isomorphism problem with invertible adjacency matrices
Omar Shehab
# Graph isomorphism problem with invertible adjacency matrices

(Asked by: username_0 on 2015-10-07)

This question is supplementary to the question asked [here](https://math.stackexchange.com/questions/1469024/which-graphs-do-have-invertible-adjacency-matrices).

One of the answers give a class of graphs for which the adjacency matrices are invertible which is defined as follows.

> Given a permutation $\pi$ of a finite set $V$, form its cycle graph
> $G$ as follows: the vertex set is $V$ and the edges are pairs $(v,w)$
> for which $\pi(v)=w$. (This is a simple directed graph.) The adjacency
> matrix will in fact be the permutation matrix corresponding to $\pi$,
> which is invertible.

Let's consider a class of graph isomorphism problems where it is promised that both of the input graphs will be from the class defined above.

Can the graph isomorphism problems from this class be solved efficiently?

**Tags:** graph-theory, linear-algebra, matrices, graph-isomorphism, permutations
> **Comments:**
> **username_1**: Note that if you work with the larger class of all graphs whose adjacency matrices are invertible, I believe the problem becomes GI-complete. (Namely, given any graph, add a new neighbor of degree 1 to each vertex. The resulting graph has invertible adjacency matrix.)  
> **username_0**: @JoshuaGrochow, interesting. Could you please point me to a paper/resource on it? I would like to know more.  
> **username_0**: I have asked the question here. http://math.stackexchange.com/questions/1470764/class-of-all-graphs-with-invertible-adjacency-matrices  
> **username_1**: I do not know a paper on this particular question. Is there something basic you didn't understand about my comment? If you understand the basics (e.g. what GI-complete means), then I'd treat the rest of my comment as a good exercise.  

---

## 1 answers

### Answer by username_2 on 2015-10-07. Score: 6 | Accepted answer

Isn't this graph just a collection of cycles? So we only need to compare that all the lengths in the two graphs match (which can be done by sorting the lengths).

> **Comments:**
> **username_0**: You mean lengths of all cycles?  
> **username_0**: I am not sure what definition of 'cycle graph' he has used here. According the the definition in Wikipedia (https://en.wikipedia.org/wiki/Cycle_graph), a cycle graph can have only one cycle. In that case, there cannot be any cycle graph for the permutation $(1 2)(3 4)$, right?  
> **username_3**: It's clearly a collection of disjoint cycles, being a 2-regular graph. And Igor's algorithm obviously works.  

---

