On L(d, 1)-Labelings of the Cartesian Product of Two Cycles

摘要

A k-L(d, 1)-labeling of a graph G is a function f from the vertex set V (G) to {0,1, ... ,k} such that vertical bar f(u) - f (v)vertical bar >= 1 if d(u, v) = 2 and vertical bar f (u) - f (v)vertical bar >= d if d(u, v) = 1. The L(d,1)-labeling number lambda(d)(G) of G is the smallest number k such that G has a k-L (d, 1)-labeling. In this paper, we show that 2d+2 <= lambda(d)(C-m square C-n) <= 2d+4 if either m or n is odd. Futhermore, the following cases are determined. (a) lambda(d)(C-3 square C-n) and lambda(d)(C-4 square C-n) for d >= 3, (b) lambda(3)(C-m square C-n) for some m and n, (c) lambda(d)(C-2m square C-2n) for d >= 5 when m and n are even.