On the L(2, 1)-labelling of block graphs
The distance-two labelling problem of graphs was proposed by Griggs and Roberts in 1988, and it is a variation of the frequency assignment problem introduced by Hale in 1980. An L(2, 1)-labelling of a graph G is an assignment of non-negative integers to the vertices of G such that vertices at distan...
| Autores principales: | , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_00207160_v88_n3_p468_Bonomo |
| Aporte de: |
| id |
todo:paper_00207160_v88_n3_p468_Bonomo |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_00207160_v88_n3_p468_Bonomo2023-10-03T14:18:27Z On the L(2, 1)-labelling of block graphs Bonomo, F. Cerioli, M.R. block graphs distance-two labelling problem graph colouring The distance-two labelling problem of graphs was proposed by Griggs and Roberts in 1988, and it is a variation of the frequency assignment problem introduced by Hale in 1980. An L(2, 1)-labelling of a graph G is an assignment of non-negative integers to the vertices of G such that vertices at distance two receive different numbers and adjacent vertices receive different and non-consecutive integers. The L(2, 1)-labelling number of G, denoted by λ(G), is the smallest integer k such that G has a L(2, 1)-labelling in which no label is greater than k. In this work, we study the L(2, 1)-labelling problem on block graphs. We find upper bounds for λ(G) in the general case and reduce those bounds for some particular cases of block graphs with maximum clique size equal to 3. © 2011 Taylor & Francis. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_00207160_v88_n3_p468_Bonomo |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
block graphs distance-two labelling problem graph colouring |
| spellingShingle |
block graphs distance-two labelling problem graph colouring Bonomo, F. Cerioli, M.R. On the L(2, 1)-labelling of block graphs |
| topic_facet |
block graphs distance-two labelling problem graph colouring |
| description |
The distance-two labelling problem of graphs was proposed by Griggs and Roberts in 1988, and it is a variation of the frequency assignment problem introduced by Hale in 1980. An L(2, 1)-labelling of a graph G is an assignment of non-negative integers to the vertices of G such that vertices at distance two receive different numbers and adjacent vertices receive different and non-consecutive integers. The L(2, 1)-labelling number of G, denoted by λ(G), is the smallest integer k such that G has a L(2, 1)-labelling in which no label is greater than k. In this work, we study the L(2, 1)-labelling problem on block graphs. We find upper bounds for λ(G) in the general case and reduce those bounds for some particular cases of block graphs with maximum clique size equal to 3. © 2011 Taylor & Francis. |
| format |
JOUR |
| author |
Bonomo, F. Cerioli, M.R. |
| author_facet |
Bonomo, F. Cerioli, M.R. |
| author_sort |
Bonomo, F. |
| title |
On the L(2, 1)-labelling of block graphs |
| title_short |
On the L(2, 1)-labelling of block graphs |
| title_full |
On the L(2, 1)-labelling of block graphs |
| title_fullStr |
On the L(2, 1)-labelling of block graphs |
| title_full_unstemmed |
On the L(2, 1)-labelling of block graphs |
| title_sort |
on the l(2, 1)-labelling of block graphs |
| url |
http://hdl.handle.net/20.500.12110/paper_00207160_v88_n3_p468_Bonomo |
| work_keys_str_mv |
AT bonomof onthel21labellingofblockgraphs AT ceriolimr onthel21labellingofblockgraphs |
| _version_ |
1807322389747335168 |