Notes on L(1,1) and L(2,1) labelings for n -cube

Suppose d is a positive integer. An L(d,1) -labeling of a simple graph G=(V,E) is a function f:V→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, λ_d(G), is the minimum of span over all L(d,1) -labelings of G. Whittlesey et al. proved that λ ₂(Q_n)≤ 2^k+2^k-q+1-2, where n≤ 2^k-q and 1≤ q≤ k+1. As a consequence, λ₂(Q_n)≤ 2n for n≥ 3. In particular, λ ₂(Q_{2^k-k-1)≤ 2^k-1. In this paper, we provide an elementary proof of this bound. Also, we study the (1,1) -labeling number of Q_n. A lower bound on λ₁(Q _n) are provided and λ₁(Q_2^k-1) are determined.