On L(d, 1)-labelings of graphs

Abstract

Given a graph G and a positive integer d, an L(d, 1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and u are adjacent, then f(u) - f(v) greater than or equal to d; if u and v are not adjacent but there is a two-edge path between them, then f(u)- f(v) greater than or equal to 1. The L(d, 1)-number of G, lambda(d)(G), is defined as the minimum m such that there is an L(d, 1)-labeling f of G with f(V) subset of or equal to {0, 1, 2,,.., m}. Motivated by the channel assignment problem introduced by Hale (Proc, IEEE 68 (1980) 1497-1514), the L(2, 1)-labeling and the L(1, 1)-labeling (as d = 2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that lambda(d)(G) less than or equal to Delta(2) + (d - 1)Delta for any graph G with maximum degree d. Different lower and upper bounds of lambda(d)(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs. (C) 2000 Elsevier Science B,V. All rights reserved.