直徑為3的極大加權(quán)雙星圖*

王 娜，杜智華

(1.新疆師范高等專科學(xué)校，新疆 烏魯木齊 830043；2.新疆師范大學(xué)，新疆 烏魯木齊 830054)

直徑為3的極大加權(quán)雙星圖*

王 娜1，杜智華2

(1.新疆師范高等?？茖W(xué)校，新疆 烏魯木齊 830043；2.新疆師范大學(xué)，新疆 烏魯木齊 830054)

加權(quán)圖；雙星圖；Perron向量

1 預(yù)備知識

設(shè)F是邊集E到多重集W的所有雙射，給定G與W，ρ=max{ρ(Gf)|Gf∈G(G,W)}，若存在映射f*∈F，并且滿足ρ=ρ(Gf*)，稱Gf*(∈g(G,W))是極大加權(quán)圖．

2 主要結(jié)論

設(shè)Gf∈g(G,W)，S(a,b)是有n=a+b+2個頂點的雙星圖，u,v是兩個中心且|N(u)v|=a，|N(v)u|=b，在這部分主要研究極大加權(quán)雙星圖(如圖1)．

圖1 極大加權(quán)雙星圖

圖2 賦權(quán)圖

設(shè)Gf*∈g(S(a,b),W)是極大加權(quán)圖，邊u1u2的權(quán)值為Wu1u2，即f*(u1u2)=wu1u2xT=(x1,x2,…,xn)是Perron向量．

現(xiàn)在標(biāo)記邊集E={e1,e2,…,em}，使得W=(wei|i=1,2,…,m)成遞增減列即，

wei≥we2≥…≥wem

引理1 設(shè)B是一個非負(fù)實對稱矩陣，λ1≥λ2≥…≥λn是B的n個特征值．如果有

λ=max‖x‖=1xTBx

則λ=λ1(ρ(B))．

引理2 設(shè)u,v是加權(quán)圖G的兩個頂點，v1,v2，…,vs∈NG(v)NG(u)，xT=(x1,x2,…,xn)為GPerron向量，且xi與vi對應(yīng)．G*是由刪去G的邊vvi再添加邊uvi得到的，相應(yīng)的令G*中的wuvi等于G中的wuvi(i=1,2,…,s)．如果xu>xv，則ρ(G)<ρ(G*)．

引理3 設(shè)Gf*∈g(G,W)是極大加權(quán)圖，頂點u是star-center．Sr為u-star，它的葉子分別為u1,u2,…,ur，v(不是u葉子)是與相鄰的點．設(shè)xT=(xp|p∈V(G))是Gf*的Perron向量，則有xu>xui以及xv≥xui(1≤i≤r)．

引理4 設(shè)gf∈g(G,W)，加權(quán)——鄰接矩陣Af=(wvivj)，則f與Perron向量xT=(x1,x2,…,xn)一致．

引理5 設(shè)Gf*∈g(G,W)是極大加權(quán)圖，頂點u是star-center．Sr為u-star，它的葉子分別為u1,u2,…,ur，v(不是u葉子)是與相鄰的點．設(shè)xT=(xp|p∈V(G))是Gf的Perron向量，則有xu>xui以及xv≥xui(1≤i≤r)．

引理6 如果1≤axu．

證明 假設(shè)結(jié)論不成立，即xv≤xu．設(shè)p1,p2,…,pb是v的葉子，那么將邊vqi(i=1,2,…,b-a)刪去，再添加邊uqi(i=1,2,…,b-a)并給其賦權(quán)值wvqi．這樣我們得到一個新圖Gf*．很明顯Gf*∈g(S(s,b),W)，但是由引理2可知ρ(Gf)>ρ(Gf*)，從而矛盾．故有xv>xu．

證明 首先,由引理3可知xuxv≥xuxqi，xuxv≥xvxpj，所以由引理4可得wuv=w1．假設(shè)w2=w3=…=wn-1，由a=b,Gf*有兩個自變?nèi)旱能壍?，其中xu,xv在一個軌道，其他的頂點在另外的一個軌道．由Perron向量的唯一性得到xu=xv(xpj=xqi,1≤i,j≤a)．下面證明充分性．假設(shè)存在某個i,j(2≤i,j≤a,i≠j,)使得wi≠wj．設(shè)ρ=ρ(Gf*)，從而可得，

(1)

分別從wuqi(1≤i≤a).wvpj(1≤j≤b)選取一個最大與最小者，不妨設(shè)為wuq1與wvp1，由(1)式可是wuq1

ρ(Gf)≥x'TA(Gf)x'=xTA(Gf*)x=ρ(Gf*)

由于Gf*是極大加權(quán)圖，Gf∈g(S(a,b),W)以及ρ(Gf)=x'TA(Gf)x'=ρ(Gf*)，那么由引理1可知x'為Gf的Perron向量．而x'u=x'v=xu=xv，從而有

這與(1)式矛盾，故w2=w3=…=wn-1．

定理8 設(shè)S(a,b)是有n=a+b+2個頂點的雙星圖，u,v是兩個中心．任意給定一個權(quán)值集合W={w1,w2,…,wn-1|w1≥w2≥2≥…≥wn-1}，SW(a,b)(圖2)，則SW(a,b)是g(S(a,b),W)中極大加權(quán)圖．

證明 設(shè)Gf*=SW(a,b)∈g(S(a,b),W)是極大加權(quán)圖，其Perron向量xT=(xp|p∈V(G))．

首先設(shè)a=b．若w1≥w2=…=wn-1，則由引理7可得xu=xv．進一步有xpj=xqi(1≤i,j≤a)．那么由引理5得到，xuxv>xvxpj=xuxqi(1≤i,j≤a)．從而根據(jù)引理4可知Gf*=SW(a,b)是極大加權(quán)圖．其次，若存在1≤i,j≤a(i≠j)使得wi≠wj，可知xu≠xv．不失一般性，設(shè)xu

xuxv>xvxpj≥min{xvxpj|j=1,2,…,b}≥

max{xuxqi|i=1,2,…,a}

(2)

再由引理4可知，wuv>wvpj≥min{wvpj|j=1,2,…,b}≥max{wuqi|i=1,2,…,a}，因此Gf*=SW(a,b)是極大加權(quán)圖．最后假設(shè)a

3 結(jié)束語

在上面的討論中，我們首先確立了直徑為3的雙星圖的特征向量的分量之間的關(guān)系，進一步研究了當(dāng)兩個星的點數(shù)相等時，雙星圖的特征向量與加權(quán)映射的特性，從而找到了極大加權(quán)雙星圖．我們可以根據(jù)這一思路進一步考慮直徑為4的樹的極大加權(quán)圖．

[1]DCvetkoic,MDoob.SachsofGraphs-TheoyandApplications[J].thirdedJohannAmbrosiusbarthVerlag,1995, 20: 45-48.

[2]DCvetkovic,PRowlinson,SSimic.Eigenspaceofgraphs[M].Combridge:CombridgeUniversitypress,1997.

[3]YuanJinsongandShuJinlong.Ontheweightedtreeswhichhavethesecondlargestspectralradius[J].ORtransactions, 2006,10: 181-87.

[4]王娜,杜智華.加權(quán)圖的perron向量[J].蘭州文理學(xué)院學(xué)報,2015(2)：40-43.

10.13877/j.cnki.cn22-1284.2015.08.010

2015-04-10

國家自然科學(xué)基金項目“有向圖的限制性連通度的研究”(11301452)；新疆師范高等?？茖W(xué)校校級課題“新疆高等師范院?！稊?shù)學(xué)分析》課程建設(shè)本土化研究”(XJJY201431)；校級精品課程“數(shù)學(xué)分析”

王娜,女,新疆烏魯木齊人,講師．

O

A

1008-7974(2015)04-0024-03