L(3, 2, 1)-LABELING FOR CYLINDRICAL GRID: THE CARTESIAN PRODUCT OF A PATH AND A CYCLE

Abstract

An L(3,2,1)-labeling for the graph G = (V,E) is an assignment f of a label to each vertices of G such that |f(u) - f(v)| >= 4 - k when dist (u,v) = k <= 3. The L(3,2,1)-labeling number, denoted by lambda 3,2,1(G), for G is the smallest number N such that there is an L(3,2,1)-labeling for G with span N. In this paper, we compute the L(3,2,1)-labeling number lambda 3,2,1(G) when G is a cylindrical grid, which is the cartesian product P-m rectangle C-n of the path and the cycle, when m >= 4 and n >= 138. Especially when n is a multiple of 4, or m = 4 and n is a multiple of 6, then we have lambda 3,2,1(G) - 11. Otherwise lambda 3,2,1(G) - 12.