Constant 2-Labellings And An Application To (R, A, B)-Covering Codes
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2017-11-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1973 |
| _version_ | 1797713178087391232 |
|---|---|
| author | Gravier Sylvain Vandomme Èlise |
| author_facet | Gravier Sylvain Vandomme Èlise |
| author_sort | Gravier Sylvain |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T07:32:16Z |
| format | Article |
| id | doaj.art-d900131d1f6546f9b08f72381cd671f6 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T07:32:16Z |
| publishDate | 2017-11-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-d900131d1f6546f9b08f72381cd671f62023-09-02T21:43:07ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922017-11-0137489191810.7151/dmgt.1973dmgt.1973Constant 2-Labellings And An Application To (R, A, B)-Covering CodesGravier Sylvain0Vandomme Èlise1CNRS, Institut Fourier, Grenoble, FranceUniversity of Liège, Liège, BelgiumWe 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.https://doi.org/10.7151/dmgt.1973covering codesweighted codesinfinite gridvertex-weighted graphs. |
| spellingShingle | Gravier Sylvain Vandomme Èlise Constant 2-Labellings And An Application To (R, A, B)-Covering Codes Discussiones Mathematicae Graph Theory covering codes weighted codes infinite grid vertex-weighted graphs. |
| title | Constant 2-Labellings And An Application To (R, A, B)-Covering Codes |
| title_full | Constant 2-Labellings And An Application To (R, A, B)-Covering Codes |
| title_fullStr | Constant 2-Labellings And An Application To (R, A, B)-Covering Codes |
| title_full_unstemmed | Constant 2-Labellings And An Application To (R, A, B)-Covering Codes |
| title_short | Constant 2-Labellings And An Application To (R, A, B)-Covering Codes |
| title_sort | constant 2 labellings and an application to r a b covering codes |
| topic | covering codes weighted codes infinite grid vertex-weighted graphs. |
| url | https://doi.org/10.7151/dmgt.1973 |
| work_keys_str_mv | AT graviersylvain constant2labellingsandanapplicationtorabcoveringcodes AT vandommeelise constant2labellingsandanapplicationtorabcoveringcodes |