New upper bounds on the L(2,1)-labeling of the skew and converse skew product graphs

作者：Duan, Ziming^*; Lv, Pingli; Miao, Lianying; Miao, Zhengke; Wang, Cuiqi

来源：Theoretical Computer Science, 2011, 412(22): 2393-2397.

DOI：10.1016/j.tcs.2011.01.031

• L(2,1)-labeling
• Skew product
• Converse skew product
• Frequency assignment

An L(2, 1)-labeling of a graph G is defined as a function f from the vertex set V(C) into the nonnegative integers such that for any two vertices x, y, vertical bar f(x) - f(y)vertical bar >= 2 if d(x, y) = 1 and vertical bar f(x) - f(y)vertical bar >= 1 if d(x, y) = 2, where d(x, y) is the distance between x and y in G. The L(2, 1)-labeling number lambda(2.1)(G) of G is the smallest number k such that G has an L(2, 1)-labeling with k = max{f(x)vertical bar x is an element of V(G)). In this paper, we consider the graph formed by the skew product and converse skew product of two graphs, and give new upper bounds of the L(2, 1)-labeling number, which improves the upper bounds obtained by Shao and Zhang [Z.D. Shao, D. Zhang, Improved upper bounds on the L(2, 1)-labeling of the skew and converse skew product graphs, Theoret. Comput. Sci. 400 (2008) 230-233] in many cases.

• 出版日期2011-5-13
• 单位江苏师范大学; 中国矿业大学（北京）