|
Эта публикация цитируется в 1 научной статье (всего в 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.
Поступила 4 августа 2015 г., опубликована 11 сентября 2015 г.
Образец цитирования:
D. S. Krotov, “On the number of maximum independent sets in Doob graphs”, Сиб. электрон. матем. изв., 12 (2015), 508–512
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr606 https://www.mathnet.ru/rus/semr/v12/p508
|
Статистика просмотров: |
Страница аннотации: | 181 | PDF полного текста: | 48 | Список литературы: | 44 |
|