zbMATH — the first resource for mathematics

Toroidal boards and code covering. (English) Zbl 07198013
Summary: We denote by $$\mathbb{F}_q$$ the field with $$q$$ elements. A radius-$$r$$ extended ball with center in a 1-dimensional vector subspace $$V$$ of $$\mathbb{F}^3_q$$ is the set of elements of $$\mathbb{F}^3_q$$ with Hamming distance to $$V$$ at most $$r$$. We define $$c(q)$$ to be the size of a minimum covering of $$\mathbb{F}^3_q$$ by radius-1 extended balls. We define a semiqueen to be a piece of a toroidal chessboard that extends the covering range of a rook by the southwest-northeast diagonal containing it. Let $$\xi_D(n)$$ be the minimum number of semiqueens of the $$n\times n$$ toroidal board necessary to cover the entire board except possibly for the southwest-northeast diagonal. We prove that, for $$q\geq 7$$, $$c(q)=\xi_D(q-1)+2$$. Moreover, our proof exhibits a method to build such covers of $$\mathbb{F}^3_q$$ from the semiqueen coverings of the board. With this new method, we determine $$c(q)$$ for the odd values of $$q$$ and improve both existing bounds for the even case.
MSC:
 94B Theory of error-correcting codes and error-detecting codes
Software:
CPLEX; GLPK; Gurobi
Full Text:
References:
 [1] A. P. Burger, C. M. Mynhardt and W. D. Weakley, The domination number of the toroidal queens graph of size3k×3k,Australas. J. Combin.28(2003), 137-148. · Zbl 1030.05094 [2] A. P. Burger, E. J. Cockayne and C. M. Mynhardt, Queens graphs for chessboards on the torus,Australas. J. Combin.24(2001), 231-246. · Zbl 0979.05080 [3] E. J. Cockayne, Chessboard domination problems,Discrete Math.86(1990), 13-20. · Zbl 0818.05057 [4] G. Cohen, I. Honkala, S. Litsyn and A. Lobstein,Covering Codes, NorthHolland, Amsterdam, 1997. · Zbl 0874.94001 [5] L. Euler, Recherche sur une nouvelle espèce de quarrès magiques,Leonardi Euleri Opera Omnia7(1923), 291-392. [6] A. B. Evans, Latin squares without orthogonal mates,Des. Codes Cryptogr.40 (2006), 121-130. · Zbl 1180.05022 [7] GNU Linear Programming Kit, Version 4.52,http://www.gnu.org/software /glpk/glpk.html. [8] Gurobi Optimization Inc., Gurobi Optimizer Reference Manual, 2015, http://www.gurobi.com. [9] IBM ILOG CPLEX Optimizer,2010,http://www-01.ibm.com/software/ integration/optimization/cplex-optimizer/. [10] G. Kéri,Tables for bound on covering codes, (accessed 2017),http://archive. is/8LCxi. · Zbl 1164.94012 [11] E. Maillet, Sur les carrés Latins d’Euler,Assoc. Franc. Caen.23(1894), 244- 252. · JFM 26.0239.01 [12] A. N. Martinhão,Problemas combinatórios envolvendo estruturas em espaços de Hamming, Universidade Estadual de Maringá, Ph.D. Thesis, 2016. [13] A. N. Martinhão and E. L. Monte Carmelo, Short covering codes arising from matchings in weighted graphs,Math. Comp.82(2012), 605-616. · Zbl 1293.94135 [14] C. Mendes, E. L. Monte Carmelo and M. V. Poggi, Bounds for short covering codes and reactive tabu search,Discrete Appl. Math.158(2010), 522-533. · Zbl 1186.94484 [15] E. L. Monte Carmelo and C. F. X. De Mendonça Neto, Extremal problems on sum-free sets and coverings in tridimensional spaces,Aequat. Math.78(2009), 101-112. · Zbl 1247.94071 [16] E. L. Monte Carmelo and I. N. Nakaoka, Short coverings in tridimensional spaces arising from sum-free sets,European J. Combin.29(2008), 227-233. · Zbl 1181.94133 [17] E. L. Monte Carmelo, I. N. Nakaoka and J. R. Geronimo, A covering problem on ﬁnite spaces and rook domains,Int. J. Appl. Math.20(2007), 875-886. · Zbl 1220.94058 [18] I.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.