Generalised Isospectrality of Graphs Q: Is there a graph matrix-representation (not necessarily an $n \times n$ matrix for an $n$-graph) such that isospectrality implies graph-isomorphism? For instance, would the simple distance-matrix do the job?
Background: The 'can you hear the shape of a drum?' question can be answered of undirected graphs in the negative, but I do not know if the results are only for the adjacency and/or Laplacian matrix representations.
 A: Here is a ridiculous solution using a $1 \times 1$ matrix! First, encode an $n \times n$ adjacency matrix $A$ by $a \lt 2^{\binom{n}2}$ where $a$ is the binary integer obtained by listing the above diagonal entries row by row. If you just want isospectrality to imply isomorphism then just encode it as $[a].$ 
Assuming that you want isospectrality equivalent to idomorphism, consider  all $n!$ adjacency matrices  getting an multi-set of $n!$ integers which we can give the natural order. Finally, encode the graph as the $1\times 1$ matrix $[2^{a_1+1}3^{a_2+1}\cdots]$ using the first $n!$ primes. The $+1$ is an inelegant way to avoid edge free graphs of various sizes being represented by $[1].$
This could be greatly enhanced, for example use instead the base $3$ integer with $n!-1$ $2$’s separating $a_12a_22a_32\cdots.$
‘Actually, one could just use the lexicographically least $n \times n$ adjacency matrix. This would have the vertices in decreasing order of degree. That alone is no help for regular graphs, but for others it might cut the number of cases.
A: Distance matrix is not going to help, as examples of non-isomorphic co-spectral strongly regular graphs would tell you.
The smallest examples like this exist on 16 vertices: Shrikhande graph.
In general, there seem to be logic-related obstacles for non-isomorphism certificates of this sort, related to 1st order logics with counting. This has started with the famous paper 
An Optimal Lower Bound on the Number of
Variables for Graph Identification by Cai, Furer and Immerman.
