Return to Answer

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 $2d_i2d_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 $4b_i4b_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|.$

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

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

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 $2d_i2d_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 $4b_i4b_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|.$

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. Provide a isolated vertex to $H$ so that both have $n=7$ vertices.

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