【摘要】 给定图G和正整数d,图G的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。图G的L(d,1)标号数λd(G)是指最小的正整数k使得G有一个L(d,1)标号f满足f(V){0,1,2,…,k}。已知对于最大度为Δ的一般图有λd(G)≤Δ2+(d-1)Δ。讨论了Halin图的L(d,1)标号问题,证明了λd(G)≤Δ+3(2d-1)。更多还原

【Abstract】 Given a graph G and a positive integer d,an L(d,1) labeling of G is a function f from the vertex set V(G) to the set of all nonnegative integers such that for each x,y∈V(G),｜f(x)-f(y)｜≥d if d_G(x,y)=1 and ｜f(x)-f(y)｜≥1 if d_G(x,y)=2.The L(d,1) labeling number of G,denoted by λ_d(G),is the smallest number k such that G has an L(d,1) labeling f with f(V)｛0,1,2,…,k｝.It is known that λ_d(G)≤Δ~2+(d-1)Δ for any graph G with maximum degree Δ.In this paper,we consider the L(d,1) labeling number on Halin graphs and prove that λ_d(G)≤Δ+3(2d-1) for Halin graph G.更多还原