Artículo
Bonomo, F.; Cerioli, M.R. "On the L(2, 1)-labelling of block graphs" (2011) International Journal of Computer Mathematics. 88(3):468-475
Estamos trabajando para incorporar este artículo al repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
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.
Registro:
| Documento: | Artículo |
| Título: | On the L(2, 1)-labelling of block graphs |
| Autor: | Bonomo, F.; Cerioli, M.R. |
| Filiación: | CONICET and Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina Instituto de Matemática and COPPE/Sistemas e Computaçã o, Universidade Federal Do Rio de Janeiro, Rio de Janeiro, Brazil |
| Palabras clave: | block graphs; distance-two labelling problem; graph colouring |
| Año: | 2011 |
| Volumen: | 88 |
| Número: | 3 |
| Página de inicio: | 468 |
| Página de fin: | 475 |
| DOI: | http://dx.doi.org/10.1080/00207161003650075 |
| Título revista: | International Journal of Computer Mathematics |
| Título revista abreviado: | Int J Comput Math |
| ISSN: | 00207160 |
| CODEN: | IJCMA |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00207160_v88_n3_p468_Bonomo |
Referencias:
- Chang, G., Kuo, D., The L(2, 1)-labeling on graphs (1996) SIAM J. Discrete Math., 9, pp. 309-316
- Chang, G., Lu, C., Distance-two labeling of graphs (2003) Eur. J. Combin., 24, pp. 53-58
- Chang, G., Ke, W.T., Kuo, D., Lin, D.F., Yeh, R., On L(d, 1)-labelings of graphs (2000) Discrete Math., 220, pp. 57-66
- Fishburn, P., Roberts, F., Full color theorems for L(2, 1)-colorings (2006) SIAM J. Discrete Math., 20, pp. 428-443
- Georges, J., Mauro, D., On regular graphs optimally labeled with a condition at distance two (2003) SIAM J. Discrete Math., 17, pp. 320-331
- Gonçalves, D., On the L(p, 1)-labelling of graphs (2008) Discrete Math., 308, pp. 1405-1414
- Griggs, J., Yeh, R., Labeling graphs with a condition at distance two (1992) SIAM J. Discrete Math., 5, pp. 586-595
- Hale, W., Frequency Assignment: Theory and Applications (1980) Proc. IEEE, 68 (12), pp. 1497-1514
- Havet, F., Reed, B., Sereni, J.S., L(2 1)-labelling of graphs (2008) Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 621-630. , San Francisco, California, January
- Král, D., Škrekovski, R., A theorem about the channel assignment problem (2003) SIAM J. Discrete Math., 16, pp. 426-437
- Kuo, D., Yan, J., On L(2, 1)-labelings of Cartesian products of paths and cycles (2004) Discrete Math., 283, pp. 137-144
- Liu, D.F., Yeh, R., On distance-two labelings of graphs (1997) Ars Combinatoria, 47, pp. 13-22
Citas:
---------- APA ----------
Bonomo, F. & Cerioli, M.R. (2011) . On the L(2, 1)-labelling of block graphs. International Journal of Computer Mathematics, 88(3), 468-475.http://dx.doi.org/10.1080/00207161003650075
---------- CHICAGO ----------
Bonomo, F., Cerioli, M.R. "On the L(2, 1)-labelling of block graphs" . International Journal of Computer Mathematics 88, no. 3 (2011) : 468-475.http://dx.doi.org/10.1080/00207161003650075
---------- MLA ----------
Bonomo, F., Cerioli, M.R. "On the L(2, 1)-labelling of block graphs" . International Journal of Computer Mathematics, vol. 88, no. 3, 2011, pp. 468-475.http://dx.doi.org/10.1080/00207161003650075
---------- VANCOUVER ----------
Bonomo, F., Cerioli, M.R. On the L(2, 1)-labelling of block graphs. Int J Comput Math. 2011;88(3):468-475.http://dx.doi.org/10.1080/00207161003650075
