|
This article is cited in 1 scientific paper (total 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.
Received August 4, 2015, published September 11, 2015
Citation:
D. S. Krotov, “On the number of maximum independent sets in Doob graphs”, Sib. Èlektron. Mat. Izv., 12 (2015), 508–512
Linking options:
https://www.mathnet.ru/eng/semr606 https://www.mathnet.ru/eng/semr/v12/p508
|
Statistics & downloads: |
Abstract page: | 165 | Full-text PDF : | 34 | References: | 36 |
|