The (s,t)-Relaxed L(2,1)-Labeling of Some Balanced Hypercubes

DOI

10.2991/icaita-16.2016.66How to use a DOI?

Keywords

relaxed L(2,1)-labeling problem; balanced hypercube; channel assignment problem; graph labeling

Abstract

For two vertices u and v in a graph G, we denote by dG(u,v) the distance between u and v. If dG(u,v)=i, we say the vertex v is an i-neighbor of u. Let s,t and k be nonnegative integers. An (s,t) –relaxed k-L(2,1) –labeling f of G is an assignment of labels from {0,1,…,K} to the vertices of G if each of the following three conditions is met: (1) f(u) f(v) if dG(u,v)=1; (2) for any vertex u of G, there are at most s 1-neighbors of u receiving labels from {f(u)-1,f(u)+1}; (3) for any vertex u of G, the number of 2-neighbors of u assigned the label f(u) is at most t. The (s,t)-relaxed L(2,1)-labeling number of G is the minimum k such that G admits an (s,t)-relaxed k-L(2,1)-labeling. Huang and Wu in [IEEE Transactions on Computers 46 (1997) 484--490] introduced the balanced hypercube BHn as an interconnection network topology for computing systems. In this paper, the values of the (s,t) –relaxed L(2,1) -labeling numbers of balanced hypercubes BH2 and BH3 with different pairs (s,t) are given.

Copyright

© 2016, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Taiyin Zhao
AU  - Xiaoqing Zhou
PY  - 2016/01
DA  - 2016/01
TI  - The (s,t)-Relaxed L(2,1)-Labeling of Some Balanced Hypercubes
BT  - Proceedings of the 2016 International Conference on Artificial Intelligence: Technologies and Applications
PB  - Atlantis Press
SP  - 267
EP  - 271
SN  - 1951-6851
UR  - https://doi.org/10.2991/icaita-16.2016.66
DO  - 10.2991/icaita-16.2016.66
ID  - Zhao2016/01
ER  -