A note on (s, t)-relaxed L(2,1)-labeling of graphs

作者：Zhao, Taiyin^*; Hu, Guangmin

来源：Journal of Combinatorial Optimization, 2017, 34(2): 378-382.

DOI：10.1007/s10878-016-9996-9

• (s, t)-relaxed L(2,1)-labeling
• Graph labeling
• Channel assignment problem
• Combinatorial problems

Let G = (V, E) be a graph. For two vertices u and v in G, we denote d(G)(u, v) the distance between u and v. A vertex v is called an i-neighbor of u if d(G)(u, v) = i. Let s, t and k be nonnegative integers. An (s, t)-relaxed k-L(2, 1)-labeling of a graph G is an assignment of labels from {0, 1, ..., k} to the vertices of G if the following three conditions are met: (1) adjacent vertices get different labels; (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 lambda(s,t)(2,1) (G) of G is the minimum k such that G admits an (s, t)-relaxed k-L(2, 1)-labeling.

• 出版日期2017-8
• 单位电子科技大学