Adjacency matrices of graphs 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? 
 A: This is an overlong comment to Aaron's reply. The Shrikande and grid graphs do not work. There is a paper by Brouwer and van Eijl in J. Alg. Combin. 1 which studies $p$-rank of adjacency matrices. If the adjacency matrices of the graphs mentioned are $A$ and $B$, then B&E note that the Smith normal forms of $A+2I$ and $B+2I$ are different. Hence there is no unimodular $L$ in $GL(n,\mathbb{Z})$ such that $L^{-1}AL=B$. The results in the B&E paper can be used to produce many pairs of srg's that are cospectral but not integrally equivalent.
I think trees might be the best bet. Using sage I've found cospectral trees on 12 vertices such that $A+mI$ and $B+mI$ have the same Smith normal form for many values of $m$, but I cannot see how to decide if they are integrally equivalent :-(
(There are pairs of cospectral trees on fewer than 12 vertices, and some of these pairs may serve just as well. I just wanted examples with determinant 1.)
A: Not an answer, but something here might help.  Zivkovic classifies small order (0,1) matrices by Smith Normal Form. and other measures.  You might count classes to see where to look for two distinct graphs with the same SNF.  http://arxiv.org/abs/math/0511636 is the paper by Miodrag Zivkovic.  (Disclosure: he kindly refers to work of mine, but introduces a typo in the retelling of the argument; still, I am rather partial to this paper.)
Gerhard "Ask Me About System Design" Paseman, 2011.01.15
A: Purely a guess but I would check the Shrikhande Graph and the 4x4 grid (both regular of degree 6 with 16 points and 48 edges). I'm not sure how one would check. They are distance regular graphs with the same parameters but the first is not distance transitive while the second is.  
