[en] 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 Z^2 whenever |a−b|>4, r>1 and we give the precise values of a and b. This is a refinement of Axenovich’s theorem proved in 2003.
Disciplines :
Mathematics
Author, co-author :
Vandomme, Elise ; Université de Liège > Département de mathématique > Mathématiques discrètes
Gravier, Sylvain; Université de Grenoble > Institut Fourier
Language :
English
Title :
Constant 2-labellings and an application to (r,a,b)-covering codes
Axenovich, M., On multiple coverings of the infinite rectangular grid with balls of constant radius (2003) Discrete Math., 268, pp. 31-48
Biggs, N., Perfect codes in graphs (1973) J. Combin. Theory Ser. B, 15, pp. 289-296
Cohen, G., Honkala, I., Litsyn, S., Lobstein, A., (1997) Covering Codes, , North-Holland Publishing Co., Amsterdam
Cohen, G., Honkala, I., Litsyn, S., Mattson, H., Jr., Weighted coverings and packings (1995) IEEE Trans. Inform. Theory, 41, pp. 1856-1867
Dorbec, P., Gravier, S., Honkala, I., Mollard, M., Weighted codes in Lee metrics (2009) Des. Codes Cryptogr., 52, pp. 209-218
Godsil, C.D., (1993) Algebraic Combinatorics, , Chapman & Hall, New York
Golomb, S.W., Welch, L.R., Algebraic coding and the Lee metric (1968) Error Correcting Codes (Proc. Sympos. Math. Res. Center, Madison, Wis., pp. 175-194. , John Wiley, New York, 1968
Golomb, S.W., Welch, L.R., Perfect codes in the Lee metric and the packing of polyominoes (1970) SIAM J. Appl. Math., 18, pp. 302-317
Gravier, S., Lacroix, A., Slimani, S., (a b)-codes in Z/nZ (2013) Discrete Appl. Math., 161, pp. 612-617
Gravier, S., Mollard, M., Payan, C., Variations on tilings in the Manhattan metric (1999) Geom. Dedicata, 76, pp. 265-273
Horak, P., On perfect Lee codes (2009) Discrete Math., 309, pp. 5551-5561
Kratochvíl, J., Perfect codes in general graphs (1988) Combinatorics (Eger, 1987), Col-loq. Math. Soc. János Bolyai, 52, pp. 357-364. , North-Holland, Amsterdam
Puzynina, S., Periodicity of perfect colorings of an infinite rectangular grid (2004) Diskretn. Anal. Issled. Oper. Ser., 1 (11), pp. 79-92
Puzynina, S., On periodicity of generalized two-dimensional infinite words (2009) Inform. and Comput., 207, pp. 1315-1328
Telle, J.A., Complexity of domination-type problems in graphs (1994) Nordic J. Comput., 1, pp. 157-171
Vandomme, E., (2015) Contributions to Combinatorics on Words in An Abelian Context and Covering Problems in Graphs, , hdl.handle.net/2268/176364, PhD Thesis, University of Grenoble and University of Liege