Abstract:
The Doob graph $D(m,n)$, where $m>0$, is a Cartesian product of $m$ copies of the Shrikhande graph and $n$ copies of the complete graph $K_4$ on four vertices. The Doob graph $D(m,n)$ is a distance-regular graph with the same parameters as the Hamming graph $H(2m+n,4)$. We give a characterization of MDS codes in Doob graphs $D(m,n)$ with code distance at least $3$. Up to equivalence, there are $m^3/36+7m^2/24+11m/12+1-(m\bmod2)/8-(m\bmod3)/9$ MDS codes with code distance $2m+n$ in $D(m,n)$, two codes with distance $3$ in each of $D(2,0)$ and $D(2,1)$ and with distance $4$ in $D(2,1)$, and one code with distance $3$ in each of $D(1,2)$ and $D(1,3)$ and with distance $4$ in each of $D(1,3)$ and $D(2,2)$.