广义Petersen图的L(d,1)-标号

On Generalized Petersen Graphs Labeled with L(d,1)-

图G的顶点集到非负整数集的一个映射f满足:对任意的x,y∈V(G),当dG(x,y)=1时,有f(x)-f(y)≥d;当dG(x,y)=2时,有f(x)-f(y)≥1。图的一个k-L(d,1)-标号是指图的一个标号L(d,1)使得min{f(v)|v∈V(G)}=k,标号数简记为λd(G)。研究了广义的Petersen图的标号L(d,1),给出一个特殊的标号方法,得到了广义的Petersen图的标号数λd(G)≤4d。

An L（ d, 1 ） - labeling of graph G is an integer labeling of the vertices in V（G） such that adjacent vertices receive labels which differ by at least d, and vertices which are distance two apart receive labels which differ by at least one. The λd - number of G is the minimum span taken over all L（d,1 ） - labelings of G. in this paper,we show that the λd - number of every generalized Petersen graph is bounded by 4d