RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2015, том 12, страницы 508–512 (Mi semr606)

Эта публикация цитируется в 1 статье

Дискретная математика и математическая кибернетика

On the number of maximum independent sets in Doob graphs

D. S. Krotov

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

Аннотация: 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)$.

Ключевые слова: Doob graph, independent set, MDS code, latin hypercube.

УДК: 519.143

MSC: 05B15

Поступила 4 августа 2015 г., опубликована 11 сентября 2015 г.

Язык публикации: английский

DOI: 10.17377/semi.2015.12.043



© МИАН, 2024