RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2015 Volume 12, Pages 508–512 (Mi semr606)

This article is cited in 1 paper

Discrete mathematics and mathematical cybernetics

On the number of maximum independent sets in Doob graphs

D. S. Krotov

Sobolev Institute of Mathematics, pr. Akademika Koptyuga, 4, 630090, Novosibirsk, Russia

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)$.

Keywords: Doob graph, independent set, MDS code, latin hypercube.

UDC: 519.143

MSC: 05B15

Received August 4, 2015, published September 11, 2015

Language: English

DOI: 10.17377/semi.2015.12.043



© Steklov Math. Inst. of RAS, 2026