On the L(p,1)-labelling of graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Discrete Mathematics Year : 2008

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


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.

Dates and versions

lirmm-00250126 , version 1 (10-02-2008)



Daniel Gonçalves. On the L(p,1)-labelling of graphs. Discrete Mathematics, 2008, 308 (8), pp.1405-1414. ⟨10.1016/j.disc.2007.07.075⟩. ⟨lirmm-00250126⟩
111 View
0 Download



Gmail Mastodon Facebook X LinkedIn More