杜先云,任秋道,文華燕

(1.成都信息工程學(xué)院 數(shù)學(xué)學(xué)院，四川 成都 610225;2.綿陽師范學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,四川 綿陽 621000；3.西南科技大學(xué) 城市學(xué)院，四川 綿陽 621000)

?

樹的邊帶寬與葉子數(shù)

杜先云1,任秋道2,文華燕3

(1.成都信息工程學(xué)院 數(shù)學(xué)學(xué)院，四川 成都 610225;2.綿陽師范學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,四川 綿陽 621000；3.西南科技大學(xué) 城市學(xué)院，四川 綿陽 621000)

摘要：圖G邊的一個(gè)標(biāo)號f是指邊集E(G)到集合{1,2,…,m}之間的一個(gè)一一映射，即:?e∈E(G),?t,1≤t≤m，使得f(e)=t.圖G的邊帶寬B′(G)=minBf′(G)，其中Bf′(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的葉子數(shù).而且k(為偶數(shù))元正則樹的邊帶寬B′(T*)≤l/2，廣義星圖T*的邊帶寬B′(T*)=l或l-1.

關(guān)鍵詞：獨(dú)立鄰邊集；邊帶寬；樹；葉子數(shù)

本文圖G是無向有限連通圖，頂點(diǎn)集與邊集分別是V(G)和E(G).圖G邊的一個(gè)標(biāo)號f是指邊集E(G)到自然數(shù)的子集{1,2,…,m}(m表示G的邊數(shù))之間的一個(gè)一一映射，即:?e∈E(G),?t∈N+,1≤t≤m，使得f(e)=t.圖G的邊帶寬B′(G)=minBf′(G)，其中Bf′(G)=max{|f(uv)-f(uw)|:uv,uw∈E(G)}.對于一個(gè)標(biāo)號f，若B′(G)=Bf′(G)，稱這個(gè)標(biāo)號為圖G的邊帶寬標(biāo)號[1-6].可以類似定義圖G的點(diǎn)帶寬，它來源于研究數(shù)值矩陣的逆，尋找圖的帶寬是一個(gè)NP問題.D.Eichhorn等人已完成了θ圖的邊帶寬[2].給出兩類3—正則圖的邊帶寬[3].本文用樹的葉子數(shù)來刻畫樹T的邊帶寬的界.

我們?nèi)菀字溃簣DG帶寬B′(G)≥Δ-1，其中Δ是圖G的最大度.下面給出一個(gè)引理.

引理1存在uv∈E(G)，使得圖G的邊帶寬B′(G)≥d(u)+d(v)-2，其中d(u)，d(v)分別表示頂點(diǎn)u和v的度[6].

證明令Γ(uv)={uiv:uiv∈E(G),1≤i≤d(v)}∪{uvj:uvj∈E(G),1≤j≤d(u)}，則有|Γ(uv)|=d(u)+d(v)-1.若f(uv)≤min{f(e):e∈Γ(uv)}，存在e′∈Γ(uv)使得f(e′)≥f(uv)+|Γ(uv)|-1.因此，Bf′(G)≥f(e′)-f(uv)≥d(u)+d(v)-2.對于f(uv)≥max{f(e):e∈Γ(uv)}，有類似結(jié)論.對于xy∈E(G)，設(shè)在Γ(xy)中標(biāo)號最小或最大標(biāo)號邊記為uv，對于邊uv應(yīng)用該結(jié)論可得：Bf′(G)≥d(u)+d(v)-2.由于標(biāo)號f的任意性，則有：存在uv∈E(G)，使得B′(G)≥d(u)+d(v)-2.

推論1設(shè)圖G是k-正則圖，則有B′(G)≥2(k-1).

圖1　圖的獨(dú)立鄰邊集分解Fig.1　A decompositiom of independent edge set of a graph

引理2保證了圖G邊集的正交分解.可以這樣來形象理解：拿著圖G一些頂點(diǎn)一抖，就把G的頂點(diǎn)分成n+1層，從而把G的邊集分為n層.如圖1.

定理1連通圖G的邊帶寬B′(G)≥「(m-1)/(d-1)?，d為圖G的直徑.

證明標(biāo)號f是圖G的邊集到集合{1,2,…,m}之間的一一映射.從標(biāo)號最小的邊到標(biāo)號最大的邊之間有一條路pn=u0u1…un，該路上點(diǎn)的鄰邊編號差的絕對值等于或小于B′(G).為了方便，令:

假設(shè)f(u1)=f(u2)=…=f(un-1)=B′(G)達(dá)到最大來估計(jì)圖G的邊帶寬.該路上的邊標(biāo)號分別是:f(u0u1)=1,f(uiui+1)=1+iB′(G)(1≤i≤n-1).

現(xiàn)在來說明路pn是點(diǎn)u0和un之間的短程線.若點(diǎn)ui(0≤i≤n-2)和uj(j≥i+2)有邊uiuj，它的標(biāo)號介于邊ui-1ui和uiui+1的標(biāo)號之間，令:

f(uiuj)=1+(i-1)B′(G)+k (1≤k

則有:f(uj)=f(ujuj+1)-f(uiuj)=(j-i+1)B′(G)-k>B′(G).

矛盾.因此點(diǎn)u0和un之間的距離是n.根據(jù)f(un-1un)=1+(n-1)B′(G)≥m，可得B′(G)≥「(m-1)/(n-1)?.由于圖G的最長路的邊數(shù)是直徑d，因此，B′(G)≥「(m-1)/(d-1)?.證畢.

圖2　圖)的邊的關(guān)聯(lián)情況Fig.2　A decompositiom of The categories of the related edges of the tragh )

定義2設(shè)T是一棵樹，懸掛點(diǎn)的集合為V′={v|d(v)=1}.如果存在點(diǎn)x，使得x和任意懸掛點(diǎn)v之間的距離都相等，即d(x,u)=d(x,v),u,v∈V′，稱樹T為理想樹，點(diǎn)x為樹根[5].

引理3理想樹T的邊帶寬不超過葉子數(shù).

給點(diǎn)u2的未編號的邊排序如下：

給點(diǎn)us的關(guān)聯(lián)邊中還未編號的邊排序如下：

對于1≤k≤s-1，

定理3樹的邊帶寬不超過葉子數(shù).

把k條路xiyi…zi(1≤i≤k)的全部始點(diǎn)xi粘合在一起構(gòu)成的圖，稱為廣義星圖，記為T*.我們知道：星圖的邊帶寬比葉子數(shù)少1.

推論2廣義星圖T*的邊帶寬比葉子數(shù)少1或等于葉子數(shù).

(ii)如果圖T*是由k條長度大于1的不同路構(gòu)成，其中最長路的長度為r.把長度小于r的所有路增加邊變成長度為r的路，類似(i)可得，B(T*)=k.

圖3　構(gòu)造樹T′=T1′+T2′Fig.3　The comtructeal

定理4樹T的邊帶寬滿足B′(T)≤l-s，0≤s≤l/2，其中l(wèi)為樹T的葉子數(shù).

由定理2可得:樹T的邊帶寬滿足:B′(T)≤B′(T′)≤max{Δ(T),s,l-s}.

發(fā)現(xiàn)有很多樹的邊帶寬不超過葉子數(shù)的一半.如：路和k(為偶數(shù))元正則樹的邊帶寬.

推論3k元正則樹T的邊帶寬滿足：當(dāng)k為偶數(shù)時(shí)，B′(T)≤kr/2；當(dāng)k為奇數(shù)時(shí)，B′(T)≤(kr+kr-1)/2，其中r(≥2)為樹T的半徑.

證明半徑為r的k元正則樹T的葉子數(shù)為kr，樹根為v.現(xiàn)在把T分解成兩顆半徑為r，樹根均為v的理想樹T1和T2.當(dāng)k為偶數(shù)時(shí)，T1和T2的葉子數(shù)均為kr/2，當(dāng)k為奇數(shù)時(shí)，T1的葉子數(shù)為(kr-kr-1)/2，T2的葉子數(shù)為(kr+kr-1)/2.根據(jù)定理4可得結(jié)論.證畢.

對于復(fù)雜的圖，由于與度為2的點(diǎn)相鄰的邊對圖的邊帶寬沒有貢獻(xiàn)，可將這樣的邊收縮掉.例如：將長度大于2的路收縮為長度為2的路，將長度大于3的圈收縮為長度為3的圈.經(jīng)過邊收縮后的圖可以更好地研究圖的邊帶寬.

參考文獻(xiàn):

[1]EICHHORN D,MUBAYI D,WEST D B.The edge-bandwidth of theta graphs[J].Graph Theory,2000(35): 89-98.

[2]PESK G W,SHASTRI A.Bandwidth of theta graphs with short paths[J].Discrete Mathematics,1992(103):177-187.

[3]Papadimitriou.The NP-completeness of the bandwidth minimization problem[J].Computing,1976(16):263-270.

[4]GAREY M R,GRAHAM R L,JOHNSON D S,et al.Complexity results for bandwidth minimization[J].SIAM J Applmath,1978,34:477-495.

[5]SMITHLINE L.Bandwidth of the compkletek-ary tree[J].Discrete Mathematics,1995,142:203-212.

[6]任秋道,黃瓊湘.完全圖的邊帶寬的另一證明[J].綿陽師范學(xué)院學(xué)報(bào),2005(2):12-17.

[7]陳玲,任秋道,岳華.兩類3-正則圖的邊帶寬[J].新疆師范學(xué)大學(xué)院學(xué)報(bào),2008(1):23-26.

[8]杜先云,任秋道.圖Cmk(P2,…，P2,Pl)的最大特征值[J].四川師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2009,32(1):64-67.

[9]任秋道,何繼標(biāo),黃瓊湘.圈的定向距離圖的性質(zhì)[J].四川師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2007,30(2):185-187.

[10]任秋道,汪元倫.圈的定向距離圖的階[J].四川師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2005,28(2):63-65.

責(zé)任編輯：時(shí)凌

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

DU Xianyun1,REN Qiudao2,WEN Huayan3

(1.College of Mathematics of Chengdu University of Information Technology,Chengdu 610225,China;2.Department of Mathematics and Information Science of Mianyang Normal University,Mianyang 621000,China;3.City College,Southwest University of Science and Technology,Mianyang 621000,China)

Abstract：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′(G)=minBf′(G),wherein Bf′(G)=max{|f(uv)-f(uw)|:uv,uw∈E(G)}.The paper obtains that the inequalities 「(m-1)/(d-1)?≤B′(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′(T)≤l/2,and the edge-bandwidth of a generalized star graph T* does B′(T*)=l or l-1.

Key words：independent adjacent edge- set;edge bandwidth；tree;number of leaves

收稿日期：2016-03-21.

基金項(xiàng)目：四川省教育廳自然科學(xué)基金項(xiàng)目(15114931).

作者簡介：杜先云(1964-)，男，教授，主要從事應(yīng)用數(shù)學(xué)的研究.

文章編號：1008-8423(2016)01-0001-04

DOI:10.13501/j.cnki.42-1569/n.2016.03.001

中圖分類號：O175

文獻(xiàn)標(biāo)志碼：A