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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Bonomo, Flavia
Publicado: 2011
Materias:
block graphs
distance-two labelling problem
graph colouring
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00207160_v88_n3_p468_Bonomo
http://hdl.handle.net/20.500.12110/paper_00207160_v88_n3_p468_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_00207160_v88_n3_p468_Bonomo
record_format dspace
spelling paper:paper_00207160_v88_n3_p468_Bonomo2023-06-08T14:41:22Z On the L(2, 1)-labelling of block graphs Bonomo, Flavia 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. 2011 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00207160_v88_n3_p468_Bonomo 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, Flavia
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.
author Bonomo, Flavia
author_facet Bonomo, Flavia
author_sort Bonomo, Flavia
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
publishDate 2011
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00207160_v88_n3_p468_Bonomo
http://hdl.handle.net/20.500.12110/paper_00207160_v88_n3_p468_Bonomo
work_keys_str_mv AT bonomoflavia onthel21labellingofblockgraphs
_version_ 1768545033978380288

Ejemplares similares