Weighted codes in Lee metrics
type: Item
instance of: scholarly article
title: Weighted codes in Lee metrics
zbMATH Open document ID: 1196.05031
author: Paul Dorbec
author: Sylvain Gravier
author: Michel Mollard
author: Iiro Honkala
published in: Designs, Codes and Cryptography
publication date: 2009-10-14T00:00:00Z
review text: The authors discuss perfect weighted coverings of radius one with the Manhattan metric in the \(n\)-dimensional infinite grid. This problem can also be stated as a graph coloring problem, as follows. Determine all possible pairs \((a,b)\), such that the \(n\)-dimensional infinite grid can be colored with two colors, where each vertex with the first color is adjacent to \(a\) vertices of the second color and each vertex with the second color is adjacent to \(b\) vertices of the first color. Independently, \textit{D. B. Khoroshilova} [Diskretn. Anal. Issled. Oper. 16, No. 1, 80-92, 97 (2009)] has shown that a sufficient condition for a desired coloring to exist is that \(n \geq (a+b-\gcd(a,b))/2\). In the current work, the constructions are presented in many theorems, so it is difficult to see whether this is actually also the result obtained here; anyway, tabulated results for \(n=9\) hint that this might be the case. Some nonexistence results are also obtained.
reviewed by: Patric R. J. Östergård
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C63
Mathematics Subject Classification ID: 52C17
Mathematics Subject Classification ID: 94B25
zbMATH DE Number: 5614973
zbMATH Keywords: coloring
zbMATH Keywords: grid graph
zbMATH Keywords: Manhattan metric
zbMATH Keywords: weighted code
zbMATH Keywords: graph coloring problem
zbMATH Keywords: infinite grid
MaRDI profile type: Publication
full work available at URL: s10623-009-9277-z
OpenAlex ID: W2078676496
cites work: On multiple coverings of the infinite rectangular grid with balls of constant radius
cites work: Perfect codes in graphs
cites work: Q4342497
cites work: Weighted coverings and packings
cites work: Perfect codes in Cartesian products of 2-paths and infinite paths
cites work: Q5556894
cites work: Perfect Codes in the Lee Metric and the Packing of Polyominoes
cites work: Variations on tilings in the Manhattan metric
DOI: 10.1007/S10623-009-9277-Z
Recommended article: Weighted perfect codes in Lee metric
Recommended article: Coding for the Lee and Manhattan Metrics With Weighing Matrices
Recommended article: Q5661387
Recommended article: Q4535944
Recommended article: Weight distribution of rank-metric codes
Recommended article: Concatenated codes for the Lee metric (Corresp.)
Recommended article: Q3887344
Recommended article: Q3739055
Recommended article: Weighted Reed-Muller codes revisited
Recommended article: Q3627120
description: scientific article; zbMATH DE number 5614973