For given positive integers j greater than or equal to k, an L(j, k)-labeling of a graph G is a function f : V(G) --> {0,1,2,...} such that \f(u) - f(v)\ greater than or equal to j when d(G)(u,v) = 1 and \f(u) - f(v)\ greater than or equal to k when d(G) (u,v) = 2. The L(j, k)-labeling number lambda(j, k)(G) of G is defined as the minimum m such that there is an L(j,k)-labeling f of G with f (V(G)) subset of or equal to {0, 1, 2,..., m}. For a graph G of maximum degree Delta greater than or equal to 1 it is the case that lambda(j,k)(G) greater than or equal to j + (Delta - 1)k. The purpose of this paper is to study the structures of graphs G with maximum degree Delta greater than or equal to 1 and lambda(j,k)(G) = j + (Delta - 1)k. (C) 2003 Elsevier Science Ltd. All rights reserved.
