On the number of maximum independent sets in Doob graphs

摘要

The Doob graph D(m; n) is a distance-regular graph withthe same parameters as the Hamming graph H(2m+n; 4). The maximumindependent sets in the Doob graphs are analogs of the distance-2 MDScodes in the Hamming graphs.We prove that the logarithm of the numberof the maximum independent sets in D(m; n) grows as 22m+n??1(1+o(1)).The main tool for the upper estimation is constructing an injective mapfrom the class of maximum independent sets in D(m; n) to the class ofdistance-2 MDS codes in H(2m + n; 4).