树的边带宽与叶子数

The Edge-bandwidth of a Tree and its Number of Leaves

图G边的一个标号f是指边集E(G)到集合{1,2,…,m}之间的一个一一映射,即:e∈E(G),■t,1≤t≤m,使得f(e)=t.图G的边带宽B'(G)=min B_f'(G),其中B_f'(G)=max{|f(uv)-f(uw)|:uv,uw∈E(G)}.给出树T的边带宽满足「(m-1)/(d-1)」≤B'(T)≤l-s,0≤s≤l/2,其中d为树T的直径,l为树T的叶子数.而且k(为偶数)元正则树的边带宽B'(T*)≤l/2,广义星图T*的边带宽B'(T*)=l或l-1.

A label f of an edge in a graph G refers to one-mapping from the edge set E（G）to the set{1, 2,…,m},namely：e∈E（G）,t,1≤t≤m,satisying f（e）= t.The edge-bandwidth of a graph B＆#39;（G）= minBf＆#39;（G）,wherein Bf＆#39;（G）= max{ ｜ f（uv）-f（uw）｜ ：uv,uw∈E（G）}.The paper obtains that the ine-qualities「（m-1）/（d-1）┐≤B＆#39;（T）≤l-s,0≤s≤l/ 2,wherein d is the diameter of a tree and l is the number of its leaves.Moreover the edge-bandwidth of a k（even）-regular tree T satisfies the inequalities B＆#39;（T）≤l/ 2,and the edge-bandwidth of a generalized star graph T＊ does B＆#39;（T＊）= l or l-1.