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.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00250126
Contributor : Daniel Gonçalves <>
Submitted on : Sunday, February 10, 2008 - 3:51:54 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM

Links full text

Identifiers

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⟩

Share

Metrics

Record views

183