摘要
Abstract
An L(2,1) labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that | f(x) - f(y)|≥ 2 ifd(x,y) = 1 and |f(x) - f(y) |≥ 1 if d(x,y) = 2. The L(2,1)- labeling number λ(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{ f(v): v ∈ V(G)) = k. Griggs and Yeh conjecture thatλ(G) ≤△2 for any simple graph with maximum degree△. In this paper, we derive the upper bounds of λ(G) of Kneser graph,Mycielski graph,Descartes graph, Halin graph, and prove that the conjecture is true for the above several classes of graphs.关键词
L(2,1)-标号/Kneser图/Mycielski图/Descartes图/Halin图Key words
L(2,1)-labeling/Kneser graph/Mycielski graph/Descartes graph/Halin graph分类
数理科学
