L(3,2,1)-LABELING FOR THE PRODUCT OF A COMPLETE GRAPH AND A CYCLE

Abstract

Given a graph G = (V, E), a function f on V is an L(3, 2, 1)-labeling if for each pair of vertices u, v of G, it holds that vertical bar f(u)-f(v)vertical bar >= 4-dist(u, v). L(3, 2, 1)-labeling number for G, denoted by lambda(3,2,1)(G), is the minimum span of all L(3, 2, 1)-labeling f for G. In this paper, when G = K-m square C-n is the Cartesian product of the complete graph K-m and the cycle C-n, we show that the lower bound of lambda(3,2,1)(G) is 5m-1 for m >= 3, and the equality holds if and only if n is a multiple of 5. Moreover, we show that lambda(3,2,1)(K-3 square C-n) = 15 when n >= 28 and n not equivalent to 0 (mod 5).