On the L(p,1)-labelling of graphs
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.