譚尚旺,王奇龍

(中國石油大學(xué)理學(xué)院,山東青島 266580)

給定直徑和懸掛點數(shù)的樹的拉普拉斯系數(shù)

譚尚旺,王奇龍

(中國石油大學(xué)理學(xué)院,山東青島 266580)

拉普拉斯系數(shù)；維納指標(biāo)；Laplacian-like能量；懸掛點

1 問題的提出

本文討論的圖都是無環(huán)無重邊的簡單圖。令G是一個具有n=|V(G)|個頂點和e(G)個邊的圖。用A(G)和D(G)分別表示G的鄰接矩陣和頂點度對角矩陣,則矩陣L(G)=D(G)-A(G)稱為G的拉普拉斯矩陣,L(G)的特征多項式det(λIn-L(G))稱為G的拉普拉斯多項式,記為φ(G,λ)。令ck(G)(0≤k≤n)表示φ(G,λ)系數(shù)的絕對值,則熟知,c0(G)=1,c1(G)=2e(G),cn-1(G)=nτ(G), cn(G)=0,其中τ(G)是G的生成樹的個數(shù)[1]。如果G是一個樹,則cn-2(G)和cn-3(G)分別等于G的維納指標(biāo)和修改超維納指標(biāo)。關(guān)于系統(tǒng)內(nèi)指標(biāo),超維納指標(biāo)和修改超維納指標(biāo)有關(guān),結(jié)論見文獻[2-5]。

令G和H是兩個n點圖。如果對所有的0≤k≤n,都有ck(G)≤ck(H),則記為G≤H。如果G≤H且存在某個0≤k≤n,使得ck(G)≠ck(H),則記為G?H。

令S(G)表示在G的每個邊上插入一個新的2度點后得到的細分圖,mk(G)表示G恰好包含k個邊的匹配的個數(shù)。對每個n點的無圈圖T,Zhou和Gutman[6]已經(jīng)證明利用這個結(jié)論,Zhou和Gutman[6]證明了Gutman和Pavlovic'[7]提出的一個猜想。

定理1令Pn和Sn分別表示具有n個頂點的路和星,T是不同于Pn和Sn的任意n點樹,則對所有的k=0,1,…,n,都有ck(Sn)≤ck(T)≤ck(Pn)。

借助式(1),已經(jīng)得到了一些遞減所有拉普拉斯系數(shù)的圖的變換,并且也得到了很多關(guān)于樹的拉普拉斯系數(shù)的結(jié)論。Mohar[8]給出了兩個樹的變換,并且利用這兩個變換給出了定理1的一個新的證明和加強。Zhang等[9]回答了Mohar[10]提出的用拉普拉斯系數(shù)定序樹的一些問題,并且確定了偏序≤下n點樹的幾個序。Ilic'[11]刻畫了偏序≤下給定直徑的n點樹的最小元。Ilic'等[12]刻畫了偏序≤下給定懸掛點數(shù)或2度點數(shù)的樹的最小元,特別是確定了n點樹的第二個最小元和第二個最大元。Ilic'[13]確定了偏序≤下給定匹配數(shù)的樹的最小元。Lin和Yan[14]刻畫了偏序≤下給定二部劃分的樹的最小元。

定理2令G和H是兩個n點圖。如果G≤H,則LEL(G)≤LEL(H)；如果G?H,則LEL(G)＜LEL(H)。

樹的拉普拉斯系數(shù)涉及到樹的維納指標(biāo)、修改超維納指標(biāo)、關(guān)聯(lián)能量和Laplacian-like能量。

2 預(yù)備知識

對于圖G,令μ(G)表示L(G)的最大特征值, dG(v)表示G的頂點v在G中的度。G的1度頂點稱為G的懸掛點,G關(guān)聯(lián)于懸掛點的邊稱為G的懸掛邊。G的一個路v0v1…vk稱為G在頂點v0處長為k的懸掛路,如果它滿足

定義1令w是非平凡連通圖G的一個頂點, G(p,q)表示分別在w處增加懸掛路wv1v2…vp和wu1u2…uq得到的圖。如果p≥q≥1,則從G(p,q)到G(p+1,q-1)的過程稱為G(p,q)的一個π變換,而從G(p+1,q-1)到G(p,q)的過程稱為G(p +1,q-1)的一個π-1變換。

引理1[13]如果p≥q≥1,則G(p,q)≤G(p +1,q-1)。

引理2如果G是一個二部圖并且p≥q≥1,則G(p,q)?G(p+1,q-1)。

證明既然G是二部連通圖,于是μ(G(p,q))＞μ(G(p+1,q-1))[21],從而

這表明存在一個k(2≤k≤n-2),使得ck(G(p, q))≠ck(G(p+1,q-1))。故由引理1知結(jié)論成立。

連通圖G中度大于2的頂點稱為G的分枝點,G中頂點u和v之間最短路的長度稱為u和v之間的距離。G的頂點v的離心率等于從v到其他所有頂點間距離的最大值。G中具有最小離心率的頂點稱為G的中心。樹的中心是一個或兩個鄰接的頂點[2]。

定義2 令v是樹T的一個度為m+1的頂點,記v的所有鄰接點為u,v1,v2,…,vm。假設(shè)H1,H2,…, Hm是關(guān)聯(lián)v的所有懸掛路,其中Hi的起點是vi并且長度ni≥1(i=1,2,…,m)。令T′=δ(T,v)是從T中刪除邊vv2,vv3,…,vvm,然后增加m-1個新的邊uv2,uv3,…,uvm后得到的樹。稱T′是T從v到u關(guān)于H1的一個δ變換,T是T′從u到v關(guān)于H1的一個δ-1變換。顯然,δ變換保持樹的懸掛點數(shù)不變。

引理3[12]令T是根在它的一個中心的n點樹,v是T中具有最大深度的一個分枝點,則對δ變換樹T′=δ(T,v),有T′≤T。

定義3令vu1u2…us-1us是樹T的一個路,滿足:dT(v)≥3,dT(u1)=dT(u2)=…=dT(us-1)=2, dT(us)≥3。除去u1外,假設(shè)v的其他鄰接點都在懸掛路上并且假設(shè)H=vv1v2…vt就是一個在v處的懸掛路。令T″是從T中刪除邊vu1,然后把v和u1等同得到的樹。令T?是在T″中增加新的懸掛邊vtu′1后得到的樹。

一個具有唯一分枝點v的樹稱為關(guān)于根v的星狀樹。如果一個星狀樹關(guān)于根的所有懸掛路都有幾乎相等的長度,則稱它是平衡星狀樹。用S(n,s)表示有n個頂點和s個懸掛點的平衡星狀樹。令D(n, m,r)表示在一個固定邊uv的頂點u增加m個路uui1ui2…uit(i=1,2,…,m),而在頂點v增加r個路vvj1vj2…vjt(j=1,2,…,r)后得到的n點樹,其中m+ r=s,并且mr≠0。容易發(fā)現(xiàn),D(n,m,r)有n=st+ 2個點,s個懸掛點和直徑2t+1。如果d是一個偶數(shù),則記εd=0,否則記εd=1。

引理4令T是根在它的一個中心的n點樹,v是T中具有最大深度的一個分枝點,則對δ變換樹T′=δ(T,v),有T′?T。

證明由δ變換的定義知,T至少有兩個分枝點。令us是T中與v距離最小的一個分枝點, vu1u2…us是v和us之間的唯一路,則T??T′=δ(T, v)。既然T″是T??T′的一個真子圖,于是μ(T′)＞μ(T″)[22]。另一方面,μ(T″)＞μ(T)[23]。因此, μ(T′)＞μ(T)。這表明存在一個k(2≤k≤n-2),使得ck(T′)≠ck(T)。于是由引理3得T′?T。

引理5令T是具有n頂點,s個懸掛點和直徑d的任意樹,則s(d-εd)≥2(n-1-εd)。等式成立,當(dāng)且僅當(dāng)d是一個偶數(shù)時,T?S(sd/2+1,s)；d是一個奇數(shù)時,存在整數(shù)m(1≤m≤s-1),使得T?D(s(d-1)/2+2,m,s-m)。

證明令Pd+1=u1u2…udud+1是T的一個最長路,v1=u1,v2,…,vs-1,vs=ud+1是T的所有懸掛點。容易發(fā)現(xiàn),T的所有中心都在Pd+1上。

于是sd≥2(n-1)。由式(2)知sd=2(n-1),當(dāng)且僅當(dāng)

這就得到s(d-1)≥2(n-2)。由式(3)知s(d-1)=2(n-2),當(dāng)且僅當(dāng)

圖1 一個特殊星狀樹Fig.1 A special starlike tree

引理6如果n,d,s是滿足s(d-εd)≥2(n-1-εd)且3≤s≤n-d+1的正整數(shù),則Tn,d,s具有n個頂點,s個懸掛點和直徑d。

證明由定義知,Tn,d,s有s個懸掛點,并且它的頂點數(shù)等于

如果q=0,則p≤r-1,即p+1≤r。如果q≠0,則p≤r-2,即p+2≤r。因此,Tn,d,s的直徑總是d。

3 主要結(jié)論及其證明

定理3在所有具有n個頂點,s個懸掛點和直徑d的樹中,Tn,d,s是偏序關(guān)系≤下的唯一最小元。

證明由于路Pn和星Sn分別是有2個懸掛點和n-1個懸掛點的唯一樹,于是下面假設(shè)3≤s≤n-d+1≤n-2。由引理5和引理6知,Tn,d,s是具有n個頂點,s個懸掛點和直徑d的樹。令T?Tn,d,s是任意一個具有n個頂點,s個懸掛點和直徑d的樹,Pd+1=123…d(d+1)是T的一個最長路,則T的中心都在Pd+1上。選擇一個中心作為T的根,用θ(T)表示T的分枝點個數(shù)。顯然,θ(T)≥1。下面只需證明Tn,d,s?T即可。

情形1假設(shè)θ(T)=1。此時,T是一個星狀樹。保持Pd+1不變,通過應(yīng)用π-1變換至少一次,T能被變換成Tn,d,s。由引理2得到Tn,d,s?T。

情形2假設(shè)θ(T)≥2。再劃分成兩種情形。

情形2.1假設(shè)T的所有分枝點都在Pd+1上。選擇一個與T的根有最大距離的分枝點v。令w是v在Pd+1上介于v和T的根之間的鄰接點,H1是Pd+1上關(guān)聯(lián)于v的懸掛路。通過應(yīng)用從v到w關(guān)于H1的一個δ變換,T能變換成一個具有n個頂點,s個懸掛點和直徑d的新的樹T1。顯然,θ(T1)≤θ(T)。如果θ(T1)≥2,則對T1重復(fù)上面過程,直到得到一個樹Tr為止,其中θ(Tr)=1。于是得到有n個頂點,s個懸掛點和直徑d的樹的序列T,T1,T2,…,Tr(r≥1)。因此,由情形1的結(jié)論和引理4得到Tn,d,s≤Tr?…?T1?T.

情形2.2假設(shè)T至少有一個分枝點不在Pd+1上。令v是不在Pd+1上具有最大深度的一個分枝點,P=vuu′…是從v到T的根的唯一路。由v的假設(shè)知,除去u外,v的其他所有鄰接點都在長度至少是1的懸掛路上。令H1是關(guān)聯(lián)于v的任意一個懸掛路。通過應(yīng)用從v到u關(guān)于H1的一個δ變換,T能變換成一個有n個頂點、s個懸掛點和直徑d的樹G1。顯然,θ(G1)≤θ(T)。容易發(fā)現(xiàn),u是G1的一個分枝點并且它的深度比v在T中的深度小。如果G1仍然存在分枝點不在Pd+1上,則對G1重復(fù)上面過程,直到得到一個樹Gm為止,其中Gm的分枝點都在Pd+1上。于是得到有n個頂點,s個懸掛點和直徑d的樹的序列T,G1,G2,…,Gm(m≥1)。由引理4知 Gm?…?G1?T。既然Gm滿足情形2.1的條件,于是由情形2.1的結(jié)論得Tn,d,s≤Gm?T。

推論1在所有具有n個頂點,s個懸掛點和直徑d的樹中,Tn,d,s是分別具有最小維納指標(biāo)、修改超維納指標(biāo)和LEL(=IE)的唯一樹。

推論2[12]在所有具有n個頂點和s個懸掛點的樹中,S(n,s)是偏序關(guān)系≤下的唯一最小元。

證明令T?S(n,s)是任意一個具有n個頂點和s個懸掛點的樹,并且記T的直徑為d。如果T?Tn,d,s,則由定理3得

如果Tn,d,s?S(n,s),則在Tn,d,s的最長懸掛路和最短懸掛路之間反復(fù)應(yīng)用π-1變換,直到所有懸掛路的長度變成幾乎相等為止。最后得到的樹為S(n,s),于是由引理2知

由式(5)和(6),推論得證。

推論3[11]在所有具有n個頂點和直徑d的樹中,Tn,d,n-d+1是偏序關(guān)系≤下的唯一最小元。

證明令T?Tn,d,n-d+1是任意一個具有n個頂點和直徑為d的樹,并且記T的懸掛點數(shù)為s。如果T?Tn,d,s,則由定理3得

令Pd+1是Tn,d,s的一個最長路。如果Tn,d,s?Tn,d,n-d+1,則對不在Pd+1上的Tn,d,s的懸掛路反復(fù)應(yīng)用π-1變換,直到這些懸掛路都變成懸掛邊為止。最后得到的樹為Tn,d,n-d+1,于是由引理2知

由式(7)和(8),推論得證。

引理7如果2≤s≤n-2,則S(n,s+1)?S(n,s)。

證明如果s=2,則令w是S(n,s)的任意一個中心；否則令w是S(n,s)的唯一分枝點。假設(shè)P是一個端點為w而另一個端點是懸掛點的最長路,記P的懸掛點為v。令T=S(n,s)-v+wv,則T是一個具有n個頂點和s+1個懸掛點的樹。由推論2和引理2得S(n,s+1)≤T?S(n,s)。

令A(yù)s,t表示在星圖St+1的中心增加s個長為2的懸掛路得到的樹。對一個n點樹T,令α和α′分別表示T的獨立數(shù)和匹配數(shù)。熟知,α+α′=n。注意到α′≤n/2,于是α≥n/2。

設(shè)G=(V,E)是一個簡單圖,B是V∪E的一個子集。如果B的任兩個元素既不鄰接,也不關(guān)聯(lián),則稱B為G的一個全獨立集。元素個數(shù)最多的全獨立集稱為G的最大全獨立集,并且最大全獨立集的元素數(shù)稱為G的全獨立數(shù),記為γ。

定理4在所有具有n個頂點和全獨立數(shù)為γ的樹中,An-γ-1,2γ-n+1是偏序關(guān)系≤下的唯一最小元。

證明令T?An-γ-1,2γ-n+1是任意一個具有n個頂點和全獨立數(shù)為γ的樹。記T的懸掛點數(shù)為s。既然T的所有懸掛點構(gòu)成T的一個獨立集并且T的獨立集一定是T的全獨立集,于是s≤α≤γ。注意到α≥n/2,于是γ≥n/2。既然S(n,γ)的所有懸掛路具有幾乎相等的長度,于是由γ≥n/2知S(n, γ)的所有懸掛路的長度不超過2。令x和y分別是S(n,γ)中長為2和長為1的懸掛路的個數(shù),則2x+ 1+y=n,x+y=γ。容易發(fā)現(xiàn)x=n-γ-1,y=2γ -n+1。于是S(n,γ)=An-γ-1,2γ-n+1。因此,由s≤γ,引理7和推論2,有

并且由T?An-γ-1,2γ-n+1知,對某個k(2≤k≤n-2),上面至少一個不等式是嚴格的。因此,定理得證。

推論4在所有具有n個頂點和全獨立數(shù)為γ的樹中,An-γ-1,2γ-n+1是分別具有最小維納指標(biāo)、修改超維納指標(biāo)和LEL(=IE)的唯一樹。

[1] MERRIS R.A survey of graph Laplacians[J].Linear and Multilinear Algebra,1995,39:19-31.

[2] DOBRYNIN A,ENTRINGER R,GUTMAN I.Wiener index of trees:theory and applications[J].Acta Appl Math,2001,66:211-249.

[3] RANDIC'M.Novel molecular descriptor for structureproperty studies[J].Chem Phys Lett,1993,211:478-83.

[4] GUTMAN I.A property of the Wiener number and its modifications[J].Indian J Chem,1997,36A:128-132.

[5] GUTMAN I,FURTULA B,BELI C'J.Note on the hyper-Wiener index[J].J Serb Chem Soc,2003,68:943-948.

[6] ZHOU B,GUTMAN I.A connection between ordinary and Laplacian spectra of bipartite graphs[J].Linear and Multilinear Algebra,2008,56:305-310.

[7] GUTMAN I,PAVLOVIC'L.On the coefficients of the Laplacian characteristic polynomial of trees[J].Bull Acad Serbe Sci Arts,2003,127:31-40.

[8] MOHAR B.On the Laplacian coefficients of acyclic graphs[J].Linear Algebra Appl,2007,722:736-741.

[9] ZHANG X D,Lü X P,CHEN Y H.Ordering trees by the Laplacian coefficients[J].Linear Algebra Appl, 2009,431:2414-2424.

[10] MOHAR B.Problems:Laplacian coefficients of trees [EB/OL].http://www.fmf.uni-lj.si/～mohar/, September,2006.

[11] ILIC'A.On the ordering of trees by the Laplacian coefficients[J].Linear Algebra Appl,2009,431:2203-2212.

[12] ILIC'A,ILIC'M.Laplacian coefficients of trees with given number of leaves or vertices of degree two[J].Linear Algebra Appl,2009,431:2195-2202.

[13] ILIC'A.Trees with minimal Laplacian coefficients[J]. Comp Math Appl,2010,59:2776-2783.

[14] LIN W,YAN W G.Laplacian coefficients of trees with a given bipartition[J].Linear Algebra Appl,2011, 435:152-162.

[15] LIU J,LIU B.A Laplacian-energy-like invariant of a graph[J].Match Commun Math Comput Chem,2008, 59:397-419.

[16] GUTMAN I.The energy of a graph[J].Ber Math Statist Sekt Forschungsz Graz,1978,103:1-22.

[17] STEVANOVIC'D.Laplacian-like energy of trees[J]. Match Commun Math Comput Chem,2009,61:407-417.

[18] ILIC'A,KRTINI C'Dj,ILI C'M.On Laplacian-like energy of trees[J].Match Commun Math Comput Chem, 2010,64:111-122.

[19] GUTMAN I,KIANI D,MIRZAKHAH M.On incidence energy of graphs[J].Match Commun Math Comput Chem,2009,62:573-580.

[20] JOOYANDEH M R,KIANI D,MIRZAKHAH M.Incidence energy of a graph[J].Match Commun Math Comput Chem,2009,62:561-572.

[21] TAN S W,WANG X K.On the largest eigenvalue of signless Laplacian matrix of a graph[J].J Math Res Exposition,2009,29:381-390.

[22] GUO J M.On the Laplacian spectral radius of a tree [J].Linear Algebra Appl,2003,868:379-385.

[23] 袁西英,吳寶豐,肖恩利.樹的運算及其Laplace譜[J].華東師范大學(xué)學(xué)報:自然科學(xué)版,2004,2:13-18.

YUAN Xi-ying,WU Bao-feng,XIAO En-li.Modifications of trees and the Laplacian spectrum[J].J East China Normal University(Natural Science),2004,2: 13-18.

(編輯 修榮榮)

Laplacian coefficients of trees with given diameter and number of pendant vertices

TAN Shang-wang,WANG Qi-long
(College of Science in China University of Petroleum,Qingdao 266580,China)

Let φ(T,λ)=∑nk=0(-1)kck(T)λn-kbe the characteristic polynomial of Laplacian matrix of a n-vertex tree T.It is well known that cn-2(T)and cn-3(T)are equal to the Wiener index and modified hyper-Wiener index of T,respectively.By applying some transformations of graphs,the trees with given diameter and number of pendant vertices were characterized which simultaneously minimize all Laplacian coefficients.In particular,some trees with extremal Wiener index,modified hyper-Wiener index and Laplacian-like energy were determined.

Laplacian coefficient；Wiener index；Laplacian-like energy；pendant vertex

O 157.5

A

1673-5005(2013)02-0186-05

10.3969/j.issn.1673-5005.2013.02.031

2012-08-05

國家自然科學(xué)基金項目(10871204)；中央高?；究蒲袠I(yè)務(wù)費專項(09CX04003A)

譚尚旺(1965-),男,教授,碩士,研究方向為圖論。E-mail:tswang@sina.com。