Is there an efficient way to represent all non-simple cycles of a digraph up to the number of vertices?

Question

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?

Answer 1

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.

Answer 2

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.

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$

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|.$