Given two digraphs $G$ and $H$, I want a method for creating a bijection between all non-simple cycles of for all $n \le |V(G)|$. That means, given $C_G(n)$ and $C_H(n)$ being the sets of all non-simple cycles of length $n$ in $G$ and $H$ respectively, there is a bijection between these two sets. Here, non-simple cycles refers to a closed walk on the graph where we are allowing repeated vertices and edges.

First, it is known that tr$(A^n)$ where $A$ is the adjacency matrix of a graph gives the number of non-simple cycles of length $n$. So, in polynomial time, it is possible to determine whether such a bijection can exist between graphs $G$ and $H$. The question is how to find this bijection without simply enumerating all the possible cycles and pairing them off one by one which is at least an exponential algorithm.

My first thought was to use a cycle basis. However, when considering non-simple cycles, there isn't a unique vector representation in $\mathbb{Q}^{|E(G)|}$ since edges can repeat.

Are there any other representations of the cycles in a graph besides a cycle basis that could reduce the number of cycles to be considered to a polynomial amount?

  • Not quite a polynomial amount, but if you consider k-subsets of G and of H, maybe there is a correspondence there that allows j-cycles of one k-subset to biject to j-cycles of the other k-set. Gerhard "And Perhaps Find Another Reduction" Paseman, 2018.07.12. – Gerhard Paseman Jul 13 at 4:20
  • It would be quite possible to have same number of $j$-cycles for $G$ as for $H$ but not for any subsets of each – Aaron Meyerowitz Jul 14 at 1:02

I think it is more or less an accident when two digraphs have the same number of non-simple cycles, because the number of non-isomorphic digraphs is vastly greater than the number of non-simple cycle counts. So unless your two digraphs have some other relationship I doubt that there is any general way to make a useful bijection.

Namely, since the eigenvalues are less than $|V|$ in magnitude, the number of non-simple cycles (more commonly called closed walks) of length at most $|V|$ is bounded by $|V|^{|V|+2}$. However the number of digraphs is around $2^{|V|(|V|-1)}/|V|!$ even if loops are forbidden, which is vastly larger.

  • Indeed, but the poster is talking about nonsimple cycles. Does your intuition carry over from simple to non-simple? Gerhard "Trying To Get Oriented Here" Paseman, 2018.07.11. – Gerhard Paseman Jul 12 at 5:17
  • @GerhardPaseman I corrected it to non-simple and added the necessary estimates. – Brendan McKay Jul 12 at 7:44
  • I should have been clearer in my original post, but I am not looking for graph isomorphisms. I am only interested in graphs that have different number of vertices. – LukeMSki Jul 12 at 15:27
  • Add some directed edges (maybe involving new vertices) which don't belong to any cycles to one graph if you want to change the number of vertices. – Aaron Meyerowitz Jul 12 at 18:52

If $G$ and $H$ are isomorphic then a bijection between them does what you want (Though I could assure you that two graphs are isomorphic, be telling the truth, and yet it could be hard to find a bijection.) You seem to be interested in the situation that $G$ and $H$ are $n$ vertex graphs which are not isomorphic yet $(A_g)^k$ and ($A_H)^k$ have equal trace for all $1 \leq k \leq n.$

Do you have examples? Do you have examples that don't differ by an obvious switch? Even if you have a compact description of cycles, that doesn't give you a bijection short of ordering them somehow.

Here is a kind of silly example but tell me what bijection you would want:

Both graphs have two vertices and multiple parallel directed edges. The adjacency matrices are

$A_G=\begin{bmatrix} 0 & 1 \\ 4 & 0 \end{bmatrix}$ and $A_H=\begin{bmatrix} 0 & 2 \\ 2 & 0 \end{bmatrix}$

Even for very large $k>n$ the powers have the same trace , and are equal when the trace is not zero:

$A_G^k=A_H^k=\begin{bmatrix} 2^k &0 \\ 0 & 2^k \end{bmatrix}$ for $k$ even.

For odd $k$ we have $A_G^k=\begin{bmatrix} 0 & 1 \\ 4^k & 0 \end{bmatrix}$ and $A_H^k=\begin{bmatrix} 0 & 2^k \\ 2^k & 0 \end{bmatrix}$ both with trace $0.$

A picture is hardly needed but here is one with edge labels.

enter image description here

If you do not want multiple directed edges with the same head and tail then put a vertex at each letter.

LATER

Here is another silly example. The vertices named by letters have indegree=outdegree=$1$ whereas vertex k has indegree=outdegree=$k$

enter image description here

For $j=1,2,3,4,5$ the number of $j$ cycles is $0,9,0,25,0$ in both graphs. Not fully what you wanted, but what would your bijections be for $j=2$ and $j=4$?

We have $|G|=11$ with the $25$ $4$-cycles falling into $10$ of type $4d_i4d_j$ and $15$ of type $5e_i5e_j$

We have $|H|=12$ with the $25$ $4$-cycles falling into $1$ of type $1a1a,$ $3$ of type $2b_i2b_j$ and $21$ of type $6c_i6c_j$

Q: What is your bijection?

NOTES:

  • One could replace directed $2$-cycles by directed $3$-cycles without changing the example in an essential way.

  • I'm sure a way could be found to make a similar example such that the traces of $A_G^j$ and $A_H^j$ are equal for $1 \leq j \leq |G|.$

  • This problem comes from symbolic dynamics. In particular, conjugacies of subshifts of finite type coming from vertex shifts of graphs. This means that multi-edges are not interesting. The functions will be defined between the sets of vertices of the two graphs. This is why it is important to have bijection between the cycles as a way of verifying that some of the graph structure is being preserved. – LukeMSki Jul 12 at 16:03
  • Make the miidpoints vertices and add an isolated vertex to $H$. For this simple example I can come up with something but what bijection would you want? – Aaron Meyerowitz Jul 12 at 18:47
  • OK I have added another example – Aaron Meyerowitz Jul 13 at 5:06
  • It would also help if the original poster could provide an example and how that example would be used. Gerhard "Finds Small Examples Very Motivating" Paseman, 2018.07.13. – Gerhard Paseman Jul 13 at 17:47

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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