L(1,2) and L(2,1) labelings for n-cubes

Speaker: Dr. Haiying Zhou
Time: 13:00-14:00, Wednesday, 23 Oct 2013
Venue: F203
Abstract:

Suppose d is a positive integer. An L(d,1)-labeling of a simple graph G=(V,E) is a function f: V to N={0,1,2,бн} such that |f(u)-f(v)|>=d if d_G(u,v)=1; and |f(u)-f(v)|>= 1 if d_G(u,v)=2. The span of an L(d,1)-labeling f is the absolute difference between the maximum and minimum labels. The L(d,1)-labeling number, lambda_d(G), is the minimum of span over all L(d,1)-labelings of G. Whittlesey et al. proved that lambda_2(Q_n)<= 2^k+2^{k-q+1}-2, where n<= 2^k-q and 1<= q<= k+1. As a consequence, lambda_2(Q_n)<= 2n for n>= 3. As a special case, lambda_2(Q_{2^k-k-1})<= 2^k-1. We provide an elementary proof of this bound. Also, we study the L(1,1)-labeling number of Q_n. A lower bound on lambda_1(Q_n) is provided and lambda_1(Q_{2^k-1}) is determined.