pith. sign in

arxiv: 1612.00007 · v1 · pith:OFKMFCKPnew · submitted 2016-11-30 · 🧮 math.CO · cs.DM

On the number of maximum independent sets in Doob graphs

classification 🧮 math.CO cs.DM
keywords independentmaximumsetsdoobgraphgraphsclasscodes
0
0 comments X
read the original abstract

The Doob graph $D(m,n)$ is a distance-regular graph with the same parameters as the Hamming graph $H(2m+n,4)$. The maximum independent sets in the Doob graphs are analogs of the distance-$2$ MDS codes in the Hamming graphs. We prove that the logarithm of the number of the maximum independent sets in $D(m,n)$ grows as $2^{2m+n-1}(1+o(1))$. The main tool for the upper estimation is constructing an injective map from the class of maximum independent sets in $D(m,n)$ to the class of distance-$2$ MDS codes in $H(2m+n,4)$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.