Geodesic
Constant 2-Labellings And An Application To (R, A, B)-Covering Codes
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 4, pp. 891-918.

Voir la notice de l'article provenant de la source Library of Science

We introduce the concept of constant 2-labelling of a vertex-weighted graph and show how it can be used to obtain perfect weighted coverings. Roughly speaking, a constant 2-labelling of a vertex-weighted graph is a black and white colouring of its vertex set which preserves the sum of the weights of black vertices under some automorphisms. We study constant 2-labellings on four types of vertex-weighted cycles. Our results on cycles allow us to determine (r, a, b)-codes in ℤ^2 whenever |a − b| gt; 4, r ≥ 2 and we give the precise values of a and b. This is a refinement of Axenovich’s theorem proved in 2003.
Keywords: covering codes, weighted codes, infinite grid, vertex-weighted graphs 
@article{DMGT_2017_37_4_a3,
     author = {Gravier, Sylvain and Vandomme, \`Elise},
     title = {Constant {2-Labellings} {And} {An} {Application} {To} {(R,} {A,} {B)-Covering} {Codes}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {891--918},
     publisher = {mathdoc},
     volume = {37},
     number = {4},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a3/}
}
TY  - JOUR
AU  - Gravier, Sylvain
AU  - Vandomme, Èlise
TI  - Constant 2-Labellings And An Application To (R, A, B)-Covering Codes
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 891
EP  - 918
VL  - 37
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a3/
LA  - en
ID  - DMGT_2017_37_4_a3
ER  - 
%0 Journal Article
%A Gravier, Sylvain
%A Vandomme, Èlise
%T Constant 2-Labellings And An Application To (R, A, B)-Covering Codes
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 891-918
%V 37
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a3/
%G en
%F DMGT_2017_37_4_a3
Gravier, Sylvain; Vandomme, Èlise. Constant 2-Labellings And An Application To (R, A, B)-Covering Codes. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 4, pp. 891-918. http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a3/

[1] M. Axenovich, On multiple coverings of the infinite rectangular grid with balls of constant radius, Discrete Math. 268 (2003) 31-48. doi: 10.1016/S0012-365X(02)00744-6

[2] N. Biggs, Perfect codes in graphs, J. Combin. Theory Ser. B 15 (1973) 289-296. doi: 10.1016/0095-8956(73)90042-7

[3] G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes (North-Holland Publishing Co., Amsterdam, 1997).

[4] G. Cohen, I. Honkala, S. Litsyn and H. Mattson, Jr, Weighted coverings and pack- ings, IEEE Trans. Inform. Theory 41 (1995) 1856-1867. doi: 10.1109/18.476311

[5] P. Dorbec, S. Gravier, I. Honkala and M. Mollard, Weighted codes in Lee metrics, Des. Codes Cryptogr. 52 (2009) 209-218. doi: 10.1007/s10623-009-9277-z

[6] C.D. Godsil, Algebraic Combinatorics (Chapman & Hall, New York, 1993).

[7] S.W. Golomb and L.R. Welch, Algebraic coding and the Lee metric, in: Error Correcting Codes (Proc. Sympos. Math. Res. Center, Madison, Wis., 1968), (John Wiley, New York, 1968) 175-194. doi: 10.1137/0118025

[8] S.W. Golomb and L.R. Welch, Perfect codes in the Lee metric and the packing of polyominoes, SIAM J. Appl. Math. 18 (1970) 302-317.

[9] S. Gravier, A. Lacroix and S. Slimani, (a, b)-codes in Z/nZ, Discrete Appl. Math. 161 (2013) 612-617.

[10] S. Gravier, M. Mollard and C. Payan, Variations on tilings in the Manhattan metric, Geom. Dedicata 76 (1999) 265-273. doi: 10.1023/A:1005106901394

[11] P. Horak, On perfect Lee codes, Discrete Math. 309 (2009) 5551-5561. doi: 10.1016/j.disc.2008.03.019

[12] J. Kratochvíl, Perfect codes in general graphs, in: Combinatorics (Eger, 1987), Col- loq. Math. Soc. János Bolyai, North-Holland, Amsterdam 52 (1988) 357-364.

[13] S. Puzynina, Periodicity of perfect colorings of an infinite rectangular grid, Diskretn. Anal. Issled. Oper. Ser. 1 11 (2004) 79-92.

[14] S. Puzynina, On periodicity of generalized two-dimensional infinite words, Inform. and Comput. 207 (2009) 1315-1328. doi: 10.1016/j.ic.2009.03.005

[15] J.A. Telle, Complexity of domination-type problems in graphs, Nordic J. Comput. 1 (1994) 157-171.

[16] É. Vandomme, Contributions to Combinatorics onWords in an Abelian Context and Covering Problems in Graphs (PhD Thesis, University of Grenoble and University of Liege, 2015). hdl.handle.net/2268/176364