The (s,t)-Relaxed L(2,1)-Labeling of Some Balanced Hypercubes
Taiyin Zhao, Xiaoqing Zhou · 2016
For two vertices u and v in a graph G , we denote by ( , ) G d u v the distance between u and v .If ( , ) G d 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 (2,1) k L -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 ( , ) 1 G d u v ; (2) for any vertex u of G , there are at most s 1neighbors of u receiving labels from { ( ) 1, ( ) 1} f u f u ; (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 (2,1) L -labeling number , 2,1 ( ) s t G of G is the minimum k such that G admits an ( , ) s t -relaxed k -(2,1) L -labeling.Huang and Wu in [IEEE Transactions on Computers 46 (1997) 484--490] introduced the balanced hypercube n BH as an interconnection network topology for computing systems.In this paper, the values of the ( , ) s trelaxed (2,1) L -labeling numbers of balanced hypercubes 2 BH and 3 BH with different pairs ( , ) s t are given.