Let $H$ be an adjacency matrix of a graph. Given a certain permutation matrix $P$ such that $PHP^T=H$, describe the structure of the graph corresponding to $H$ (or the matrix).
This problem is opposite of computing automorphism group of a graph. If $\sigma$ is a permutation associated with the matrix $P$, then we have $H_{\sigma(i), \sigma(j)}=H_{i,j}$. I don't think I can say anything more about the graph. Can you point me towards references where such problem is studied in detail?
What you need to do is consider the action of the permutation $P$ on the edges of the complete graph $K_{n}$. These edges will be partitioned into orbits. Then the edges of the graph with adjacency matrix $H$ must be made up of a union of these edge orbits.