On L(d, 1)-Labeling of Cartesian Product of Two Complete Graphs

摘要

An L(d, 1)-labeling for a graph G is a function f : V(G) -> {0, 1, . . . } such that vertical bar f(u) - f(v)vertical bar >= d whenever uv is an element of E (G) and vertical bar f(u) - f(v)vertical bar >= 1 whenever u and v are at distance two apart. The span of f is the difference between the largest and the smallest numbers in f(V(G)). The lambda(d)-number for G, denoted by lambda(G), is the minimum span over all L(d, 1)-labelings of G. In this paper, a constructive labeling algorithm for the L(d, 1)-labeling of Cartesian product of two complete graphs is presented. Based on this algorithm, the lambda(d)-numbers of some Cartesian product of two complete graphs are determined for 1 <= d <= 9.