On the number of maximum independent sets in Doob graphs Full article
| Journal |
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304 |
||
|---|---|---|---|
| Output data | Year: 2015, Volume: 12, Pages: 508-512 Pages count : 5 DOI: 10.17377/semi.2015.12.043 | ||
| Tags | Doob graph, independent set, MDS code, latin hypercube | ||
| Authors |
|
||
| Affiliations |
|
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).
Cite:
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
Dates:
| Submitted: | Aug 4, 2015 |
| Published online: | Sep 11, 2015 |
Identifiers:
| Web of science: | WOS:000440432400077 |
| Scopus: | 2-s2.0-85003467528 |
| Elibrary: | 25409131 |
| OpenAlex: | W2558556197 |