TY - JOUR
T1 - Notes on L(1,1) and L(2,1) labelings for n -cube
AU - Zhou, Haiying
AU - Shiu, Wai Chee
AU - Lam, Peter Che Bor
N1 - Funding Information:
This work is partially supported the FRG of Hong Kong Baptist University.
PY - 2014/10
Y1 - 2014/10
N2 - 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 dG(u,v)=1; and |f(u)-f(v)|≥ 1 if dG(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 λ 2(Qn)≤ 2k+2k-q+1-2, where n≤ 2k-q and 1≤ q≤ k+1. As a consequence, λ2(Qn)≤ 2n for n≥ 3. In particular, λ 2(Q{2k-k-1)≤ 2k-1. In this paper, we provide an elementary proof of this bound. Also, we study the (1,1) -labeling number of Qn. A lower bound on λ1(Q n) are provided and λ1(Q2k-1) are determined.
AB - 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 dG(u,v)=1; and |f(u)-f(v)|≥ 1 if dG(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 λ 2(Qn)≤ 2k+2k-q+1-2, where n≤ 2k-q and 1≤ q≤ k+1. As a consequence, λ2(Qn)≤ 2n for n≥ 3. In particular, λ 2(Q{2k-k-1)≤ 2k-1. In this paper, we provide an elementary proof of this bound. Also, we study the (1,1) -labeling number of Qn. A lower bound on λ1(Q n) are provided and λ1(Q2k-1) are determined.
KW - Channel assignment problem
KW - Distance two labeling
KW - n -cube
UR - http://www.scopus.com/inward/record.url?scp=84906948383&partnerID=8YFLogxK
U2 - 10.1007/s10878-012-9568-6
DO - 10.1007/s10878-012-9568-6
M3 - Journal article
AN - SCOPUS:84906948383
SN - 1382-6905
VL - 28
SP - 626
EP - 638
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
IS - 3
ER -