|
|
Diskretnyi Analiz i Issledovanie Operatsii, 2014, Volume 21, Issue 6, Pages 3–10
(Mi da797)
|
|
|
|
This article is cited in 11 scientific papers (total in 11 papers)
Bounds on the cardinality of a minimal $1$-perfect bitrade in the Hamming graph
K. V. Vorob'evab, D. S. Krotovab a S. L. Sobolev Institute of Mathematics, SB RAS, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
b Novosibirsk State University, 2 Pirogov St., 630090 Novosibirsk, Russia
Abstract:
We improve well-known upper and lower bounds on the minimal cardinality of the support of an eigenfunction of the Hamming graph $H(n,q)$ for $q>2$. In particular, the cardinality of a minimal $1$-perfect bitrade in $H(n,q)$ is estimated. We show that the cardinality of such bitrade is at least $2^{n-\frac{n-1}q}(q-2)^\frac{n-1}q$ in case $q\ge4$ and $3^\frac n2(1-O(1/n))$ in case $q=3$. Moreover, we propose a construction of bitrades of the cardinality $q^\frac{(q-2)(n-1)}q2^{\frac{n-1}q+1}$ for $n\equiv1\bmod q$ where $q$ is a prime power. Bibliogr. 10.
Keywords:
Hamming graph, Krawtchouk polynomial, $1$-perfect bitrade.
Received: 23.10.2014 Revised: 10.11.2014
Citation:
K. V. Vorob'ev, D. S. Krotov, “Bounds on the cardinality of a minimal $1$-perfect bitrade in the Hamming graph”, Diskretn. Anal. Issled. Oper., 21:6 (2014), 3–10; J. Appl. Industr. Math., 9:1 (2015), 141–146
Linking options:
https://www.mathnet.ru/eng/da797 https://www.mathnet.ru/eng/da/v21/i6/p3
|
| Statistics & downloads: |
| Abstract page: | 518 | | Full-text PDF : | 197 | | References: | 71 | | First page: | 9 |
|