On existence of perfect bitrades in Hamming graphs. (English) Zbl 1458.05200
Summary: A pair \((T_0,T_1)\) of disjoint sets of vertices of a graph \(G\) is called a perfect bitrade in \(G\) if any ball of radius 1 in \(G\) contains exactly one vertex in \(T_0\) and \(T_1\) or none simultaneously. The volume of a perfect bitrade \((T_0,T_1)\) is the size of \(T_0\). If \(C_0\) and \(C_1\) are distinct perfect codes with minimum distance 3 in \(G\) then \((C_0\setminus C_1,C_1\setminus C_0)\) is a perfect bitrade. For any \(q\geq 3\), \(r\geq 1\) we construct perfect bitrades of volume \((q!)^r\) in the Hamming graph \(H(qr+1,q)\) and show that for \(r=1\) their volume is minimum.
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 94B05 | Linear codes (general theory) |
Keywords:
perfect code; one-error-correcting code; spherical bitrade; perfect bitrade; MDS code; alternating groupReferences:
| [1] | Bassalygo, L. A.; Zinoviev, V. A.; Leontiev, V. K.; Feldman, N. I., Nonexistence of perfect codes over some non prime alphabets, Probl. Inf. Transm., 11, 3, 181-189 (1975) |
| [2] | Brouwer, A. E.; Haemers, W. H., (Spectra of Graphs. Spectra of Graphs, Universitext (2012), Springer-Verlag: Springer-Verlag New York), 253 · Zbl 1231.05001 |
| [3] | Etzion, T.; Vardy, A., On perfect codes and tilings: problems and solutions, SIAM J. Discrete Math., 11, 2, 205-223 (1998) · Zbl 0908.94035 |
| [4] | Hawtin, D. R.; Gillespie, N. I.; Praeger, C. E., Elusive codes in Hamming graphs, Bull. Aust. Math. Soc., 88, 2, 286-296 (2013) · Zbl 1283.94146 |
| [5] | Hedayat, A. S.; Khosrovshahi, G. B., Trades, (Colbourn, C. J.; Dinitz, J. H., Handbook of Combinatorial Designs. Handbook of Combinatorial Designs, Discrete Mathematics and its Applications (2006), Chapman Hall CRC: Chapman Hall CRC Boca Raton, London, New York), 984, 2007 |
| [6] | Heden, O., A survey of perfect codes, Adv. Math. Commun., 2, 2, 223-247 (2008) · Zbl 1274.94151 |
| [7] | Hwang, H. L., On the structure of (v, k, t) trades, J. Stat. Plan. Inference, 13, 179-191 (1986) · Zbl 0593.62071 |
| [8] | Krotov, D. S., The extended 1-perfect trades in small hypercubes, Discrete Math., 340, 10, 2559-2572 (2017) · Zbl 1386.94109 |
| [9] | Krotov, D. S.; Avgustinovich, S. V., On the number of \(1\)-perfect binary codes: A lower bound, IEEE Trans. Inf. Theory, 54, 4, 1760-1765 (2008) · Zbl 1328.94084 |
| [10] | Krotov, D.; Mogilnykh, I.; Potapov, V., To the theory of q-ary steiner and other-type trades, Discrete Math., 339, 3, 1150-1157 (2016) · Zbl 1328.05025 |
| [11] | Östergård, P. R.J., Switching codes and designs, Discrete Math., 312, 3, 621-632 (2012) · Zbl 1243.94040 |
| [12] | Phelps, K. T.; LeVan, M., Switching equivalence classes of perfect codes, Des. Codes Cryptogr., 16, 2, 179-184 (1999) · Zbl 0938.94015 |
| [13] | Potapov, V. N., Multidimensional latin bitrades, Sib. Math. J., 54, 2, 317-324 (2013) · Zbl 1268.05034 |
| [14] | Solov’eva, F. I., Exact Bounds on the Connectivity of Code-Generated Disjunctive Normal Forms, 10 (1990), Inst. Math. of the Siberian Branch of Acad. of Sciences: Inst. Math. of the Siberian Branch of Acad. of Sciences USSR, Preprint (in Russian) |
| [15] | Solov’eva, F. I., Switching methods for error-correcting codes, (Aspects of Network and Information Security. Aspects of Network and Information Security, NATO Science for Peace and Security, Series D: Information and Communication Security, vol. 17 (2008), IOS Press), 333-342 |
| [16] | Tietäväinen, A., On the nonexistence of perfect codes over finite fields, SIAM J. Appl. Math., 24, 1, 88-96 (1973) · Zbl 0233.94004 |
| [17] | Valyuzhenich, A., Minimum supports of eigenfunctions of Hamming graphs, Discrete Math., 340, 5, 1064-1068 (2017) · Zbl 1357.05094 |
| [18] | Valyuzhenich, A., Eigenfunctions and minimum 1-perfect bitrades in the Hamming graph (2020) |
| [19] | Valyuzhenich, A.; Vorob’ev, K., Minimum supports of functions on the Hamming graphs with spectral constraints, Discrete Math., 342, 5, 1351-1360 (2019) · Zbl 1407.05226 |
| [20] | Vasil’ev, Yu. L., On nongroup close-packed codes, Probl. Cybernet., 8, 337-339 (1963) · Zbl 0202.50305 |
| [21] | Vorobev, K. V.; Krotov, D. S., Bounds for the size of a minimal 1-Perfect bitrade in a Hamming graph, J. Appl. Ind. Math., 9, 1, 141-146 (2015) · Zbl 1324.05047 |
| [22] | V.A. Zinoviev, Combinatorial Methods of Constructing and Analyzing Nonlinear Correcting Codes (Doc. D. thesis), Moscow, 1988 (in Russian). |
| [23] | Zinoviev, V. A.; Leontiev, V. K., Nonexistence of perfect codes over Galois fields, Probl. Control Inform. Theory, 2, 2, 123-132 (1973) · Zbl 0318.94013 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
