Some famous cryptographical protocols rely on the construction of graphs $G_i= (V_i, E_i)$ for $i=0,1$ that are not isomorphic. For the safety of this protocol, it is central that one can not easily verify that $G_0\not\cong G_1$. So, for instance, one could easily establish that $G_0\not\cong G_1$ if $|V_0| \neq |V_1|$, or if the iterated degree matrix of $G_0$ and $G_1$ differ.
As a non-rigid terminology, let us call graphs $G_0, G_1$ "pseudo-isomorphic" if they "look isomorphic", that is, in particular, they have the same iterated degree matrix.
What are other criteria that make graphs pseudo-isomorphic? Need they be regular for instance? (If the degrees differ greatly, that could be an anchor for finding an isomorphism, or establishing that there cannot be one.)
EDIT. Here's a scenario for non-isomorphism. Suppose Alice and Bob want to play cryptographically safe rock-paper-scissors over the telephone. So they agree on three large graphs $G_0, G_1, G_2$ that are pseudo-isomorphic, but not isomorphic, one representing rock, one paper, one scissors. So if Alice makes a move (say, she picks "scissors"), she selects $G_2$, applies a random permutation $\psi:V(G_2)\to V(G_2)$ and sends the new graph $G_2' = \psi(G_2)$ to Bob. Bob does a similar thing with his favourite graph. Bob can't know to which of the original graphs $G_0, G_1, G_2$ the graph $G_2'$ corresponds to. When Bob has committed his permuted graph, both tell each other the selected graph PLUS the selected permutation, so each one can be sure the other didn't change his selection after committing.
