Motivated by the apparent lack of possible classification of integer matrices up to conjugation (see here) and by a question about possible complete graph invariants (see here), let me ask the following:
Question: Is there an example of a pair of non-isomorphic simple finite graphs which have conjugate (over $\mathbb Z$) adjacency matrices?
It is well-known that there are many graphs which have the same spectrum. This implies that their adjacency matrices are conjugate over $\mathbb C$.
In Allen Schwenk, Almost all trees are cospectral. New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971), pp. 275–307. Academic Press, New York, 1973 it was shown that almost all trees have cospectral partners. Maybe $\mathbb Z$-conjugate graphs can be found among trees?
