Suppose $X$ and $Y$ are two $n$-circulants (Cayley graphs for $\mathbb{Z}_n$) with adjacency matrices $A_X$ and $A_Y$. Since they are circulants, both $X$ and $Y$ lie in some symmetric association schemes (details below). Let $\mathcal{C}_X$ and $\mathcal{C}_Y$ be the **smallest** association schemes containing $A_X$ and $A_Y$ respectively. Suppose that $\phi: \mathcal{C}_X \to \mathcal{C}_Y$ is an isomorphism of association schemes (bijective linear map that preserves matrix multiplication, entrywise multiplication, and transposition) that also satisfies $\phi(A_X) = A_Y$. Under these conditions, is it possible for $X$ and $Y$ to be NOT isomorphic? By the results of this paper, it seems that this cannot happen if one of the graphs (and thus also the other) is distance regular.

If I understand correctly, the condition imposed on $X$ and $Y$ is equivalent to the Weisfeiler-Lehman algorithm NOT being able to distinguish them.

**Details on association schemes:**

A symmetric association scheme $\mathcal{C}$ is a matrix subalgebra of the real $n \times n$ matrices that contains identity and the all ones matrix, is closed under entrywise mutliplication and transposition, and contains only symmetric matrices. Note that the last condition also implies that all matrices in $\mathcal{C}$ commute with each other. Since it is closed under entrywise multiplication, any symmetric association scheme has an orthogonal basis of 01-matrices $A_0, \ldots, A_d$ that sum up to the all ones matrix. One of these is necessarily the identity matrix (so WLOG we let $A_0 = I$) and thus the other $A_i$ are 01 symmetric matrices with 0 on the diagonal. We can think of these as adjacency matrices of graphs, and we say that a graph lies in $\mathcal{C}$ if its adjacency matrix is the sum of some of the $A_i$. It is easy to see that the intersection of two association schemes is an association scheme, and thus if a graph lies in an association scheme, there is some unique minimal association scheme that contains it.

For a given $n \in \mathbb{N}$, let $A_s$ be the $n \times n$ matrix whose $ij$-entry is 1 if $i - j \equiv \pm s \text{ mod } n$, and is 0 elsewhere. It is not difficult to see that these $A_s$ matrices are the 01-basis of a symmetric association scheme, and that any $n$-circulant lies in this scheme. Thus any circulant graph lies in a symmetric association scheme.