Constant 2-Labellings And An Application To (R, A, B)-Covering Codes

• Autorzy: Sylvain Gravier , Èlise Vandomme
• Języki publikacji: EN

Abstrakty

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 Z2 whenever |a − b| > 4, r ≥ 2 and we give the precise values of a and b. This is a refinement of Axenovich’s theorem proved in 2003.

Słowa kluczowe

EN

covering codes; weighted codes; infinite grid; vertex-weighted graphs.

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 4
• Strony: 891-918

Daty

wydano

2017-11-27

otrzymano

2015-11-16

poprawiono

2016-07-11

zaakceptowano

2016-07-11

online

2017-09-02

Twórcy

autor

Sylvain Gravier

• ,

autor

Èlise Vandomme

• ,

Identyfikatory

DOI

10.7151/dmgt.1973