L(2,1)-Labelings on Some Products of n General Graphs

摘要

Let G be a graph and y) be the distance between two vertices x and y in G. An L(2, 1)-labeling of G is a function f from all vertices of G to the set of all nonnegative integers such that if d(x,y) = 1 then |f(x) - f(y)| ≥ 2 and if d(x,y) = 2 then |f(x) - f(y)| ≥ 1. A k-L(2, 1)-labeling is an L(2, 1)-labeling such that the maximum label is no greater than k. The L(2, 1)-labeling number of G, λ(G), is the smallest number k among all k-L(2, 1)-labelings of G. Griggs and Yeh conjectured that λ(G) ≤ Δ~2 for any simple graph with maximum degree △ > 2. In this article, the graphs formed by the direct, skew and converse skew products of any n general graphs are studied. The upper bounds of the L(2, 1)-labeling numbers for them are obtained and it is proved the obtained bounds all satisfy the Griggs and Yeh's conjecture.