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

Haiying Zhou; Wai Chee SHIU; Peter Che Bor Lam

doi:10.1007/s10878-012-9568-6

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

Haiying Zhou, Wai Chee SHIU^*, Peter Che Bor Lam

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	626-638
Number of pages	13
Journal	Journal of Combinatorial Optimization
Volume	28
Issue number	3
DOIs	https://doi.org/10.1007/s10878-012-9568-6
Publication status	Published - Oct 2014

Scopus Subject Areas

Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics

User-Defined Keywords

Channel assignment problem
Distance two labeling
n -cube

Access to Document

10.1007/s10878-012-9568-6

Cite this

@article{6b44645e4534426781beacafb0d473b6,

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

abstract = "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.",

keywords = "Channel assignment problem, Distance two labeling, n -cube",

author = "Haiying Zhou and SHIU, {Wai Chee} and Lam, {Peter Che Bor}",

note = "Funding Information: This work is partially supported the FRG of Hong Kong Baptist University.",

year = "2014",

month = oct,

doi = "10.1007/s10878-012-9568-6",

language = "English",

volume = "28",

pages = "626--638",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "3",

}

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 - 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 -

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

Abstract

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this