On the number of maximum independent sets in Doob graphs Научная публикация
| Журнал |
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304 |
||
|---|---|---|---|
| Вых. Данные | Год: 2015, Том: 12, Страницы: 508-512 Страниц : 5 DOI: 10.17377/semi.2015.12.043 | ||
| Ключевые слова | Doob graph, independent set, MDS code, latin hypercube | ||
| Авторы |
|
||
| Организации |
|
Реферат:
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).
Библиографическая ссылка:
Krotov D.S.
On the number of maximum independent sets in Doob graphs
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2015. V.12. P.508-512. DOI: 10.17377/semi.2015.12.043 WOS Scopus РИНЦ OpenAlex
On the number of maximum independent sets in Doob graphs
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2015. V.12. P.508-512. DOI: 10.17377/semi.2015.12.043 WOS Scopus РИНЦ OpenAlex
Даты:
| Поступила в редакцию: | 4 авг. 2015 г. |
| Опубликована online: | 11 сент. 2015 г. |
Идентификаторы БД:
| Web of science: | WOS:000440432400077 |
| Scopus: | 2-s2.0-85003467528 |
| РИНЦ: | 25409131 |
| OpenAlex: | W2558556197 |