From Wikipedia.

In linear algebra, two n-by-n matrices A and B are called similar if
$$    B = P^{-1} A P$$
for some invertible n-by-n matrix $P$.

If $P$ is a permutation matrix, $A$ and $B$ are **permutation similar**.

Two graphs $G,H$ are isomorphic iff their adjacency matrices 
 $A_G,A_H$ are permutation similar.

If $A_G$ and $A_H$ are not similar then $G$ and $H$ are not isomorphic.

It is possible $A_G$ and $A_H$ to be similar and $G$ and $H$ are not isomorphic.

Experimentally this doesn't happen often.

Recognizing matrix similarity is polynomial, $O(n^3)$.

$A$ and $B$ are similar if and only if they have the same rational canonical form (AKA Frobenius form).

> Is there characterization of the graphs for which
$A_G \sim A_H \implies G \cong H$?

Consider the following algorithm for graph isomorphism.

Recursively delete vertex from $G$ and from $H$ and
check the matrices for similarity. If we don't hit
bad case we will find isomorphism in polynomial time.

The exponential case is if we hit bad cases very often.

> Is there construction of non-isomorphic graphs for
which the above algorithm is exponential?