无K_(1,t)图的L(d,1)-T标号

给定一个连通图G=(V,E)及其一棵支撑树T,图G的一个L(d,1)-T标号即函数g:V(G)→{0,1,2,…},满足:(1)如果xy∈E(G),则|g(x)-g(y)|≥1;(2)如果dG(x,y)=2,则|g(x)-g(y)|≥1;(3)如果xy∈E(T),则|g(x)-g(y)|≥d.假设图G有一个L(d,1)-T标号函数g:g(V){0,1,2,…,k},则图G的所有L(d,1)-T标号函数中最小的整数k记为L(d,1)-T标号数λdT(G,T).本文证明了若G是无K1,t(3≤t≤n)的连通图,其最大度为Δ,|G|=n,T为G的任意支撑树,则λdT(G,T)≤tt--12Δ2+Δ+2d-2.

L(d,1)-T Labeling of K1,t Free Graphs

A connected graph G = （ V, E）, its spanning tree T and its labeling L （d, 1 ）-T （a function g） satisfy these conditions： if xy ∈ E（G）,then ｜g（x） -g（y） ｜≥1;if dG（x,y） =2,then Ig（x） -g（y） ｜1≥1;ifxy∈E（T）,then ｜g（x） -g（y） ｜ ≥d. The labeling number Ar（G,T） is the minimum k satisfying all the labeling functions of graph G. This paper proves that λdT（ G,T）≤t-1/t-2- △2 ＋△ ＋2d -2 if G is a K1,t-free connected Graph （3 ≤1 ≤n）, its maximum degree △, ｜ G｜ = n and its any spanning tree T.