On the L(p,1)-labelling of graphs

Daniel Gonçalves 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The L(p,q)-labelling of graphs, is a graph theoretic framework introduced by Griggs and Yeh [Labelling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586-595] to model the channel assignment problem. In this paper we improve the best known upper bound for the L(p,1)-labelling of graphs with given maximum degree. We show that for any integer p>1, any graph G with maximum degree Δ admits an L(p,1)-labelling such that the labels range from 0 to Δ^2+(p-1)Δ-2.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2008, 308 (8), pp.1405-1414. 〈10.1016/j.disc.2007.07.075〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00250126
Contributeur : Daniel Gonçalves <>
Soumis le : dimanche 10 février 2008 - 15:51:54
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

Collections

Citation

Daniel Gonçalves. On the L(p,1)-labelling of graphs. Discrete Mathematics, Elsevier, 2008, 308 (8), pp.1405-1414. 〈10.1016/j.disc.2007.07.075〉. 〈lirmm-00250126〉

Partager

Métriques

Consultations de la notice

97