Bounds for the size of a minimal 1-perfect bitrade in a Hamming graph Full article
| Journal |
Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2015, Volume: 9, Number: 1, Pages: 141-146 Pages count : 6 DOI: 10.1134/s1990478915010159 | ||||
| Tags | Hamming graph, Krawtchouk polynomial, 1-perfect bitrade | ||||
| Authors |
|
||||
| Affiliations |
|
Abstract:
We improve the available upper and lower bounds for the minimal size of the support of an eigenfunction of the Hamming graph $H(n,q)$, where $q>2$. In particular, the size of a minimal 1-perfect bitrade in $H(n,q)$ is estimated. We show that the size of such a bitrade is at least $2^{n-(n-1)/q}(q-2)^{(n-1)/q}$ for $q≥4$ and $3^{n/2}(1-O(1/n))$ for $q=3$. Moreover, for $n≡1$ mod $q$, where $q$ is a prime power, we propose a construction of bitrades of size $q^{(q−2)(n−1)/q}2^{(n-1)/q+1}$.
Cite:
Vorob'ev K.V.
, Krotov D.S.
Bounds for the size of a minimal 1-perfect bitrade in a Hamming graph
Journal of Applied and Industrial Mathematics. 2015. V.9. N1. P.141-146. DOI: 10.1134/s1990478915010159 Scopus РИНЦ OpenAlex
Bounds for the size of a minimal 1-perfect bitrade in a Hamming graph
Journal of Applied and Industrial Mathematics. 2015. V.9. N1. P.141-146. DOI: 10.1134/s1990478915010159 Scopus РИНЦ OpenAlex
Original:
Воробьёв К.В.
, Кротов Д.С.
Оценки мощности минимального 1-совершенного битрейда в графе Хэмминга
Дискретный анализ и исследование операций. 2014. Т.21. №6. С.3-10. РИНЦ
Оценки мощности минимального 1-совершенного битрейда в графе Хэмминга
Дискретный анализ и исследование операций. 2014. Т.21. №6. С.3-10. РИНЦ
Dates:
| Submitted: | Oct 23, 2014 |
| Accepted: | Nov 10, 2014 |
| Published online: | Feb 28, 2015 |
Identifiers:
| Scopus: | 2-s2.0-84923844499 |
| Elibrary: | 24010875 |
| OpenAlex: | W2077459447 |