给定直径和悬挂点数的树的拉普拉斯系数

谭尚旺,王奇龙

(中国石油大学理学院,山东青岛 266580)

给定直径和悬挂点数的树的拉普拉斯系数

谭尚旺,王奇龙

(中国石油大学理学院,山东青岛 266580)

拉普拉斯系数；维纳指标；Laplacian-like能量；悬挂点

1 问题的提出

本文讨论的图都是无环无重边的简单图。令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,λ)系数的绝对值,则熟知,c0(G)=1,c1(G)=2e(G),cn-1(G)=nτ(G), cn(G)=0,其中τ(G)是G的生成树的个数[1]。如果G是一个树,则cn-2(G)和cn-3(G)分别等于G的维纳指标和修改超维纳指标。关于系统内指标,超维纳指标和修改超维纳指标有关,结论见文献[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个边的匹配的个数。对每个n点的无圈图T,Zhou和Gutman[6]已经证明利用这个结论,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),已经得到了一些递减所有拉普拉斯系数的图的变换,并且也得到了很多关于树的拉普拉斯系数的结论。Mohar[8]给出了两个树的变换,并且利用这两个变换给出了定理1的一个新的证明和加强。Zhang等[9]回答了Mohar[10]提出的用拉普拉斯系数定序树的一些问题,并且确定了偏序≤下n点树的几个序。Ilic'[11]刻画了偏序≤下给定直径的n点树的最小元。Ilic'等[12]刻画了偏序≤下给定悬挂点数或2度点数的树的最小元,特别是确定了n点树的第二个最小元和第二个最大元。Ilic'[13]确定了偏序≤下给定匹配数的树的最小元。Lin和Yan[14]刻画了偏序≤下给定二部划分的树的最小元。

定理2令G和H是两个n点图。如果G≤H,则LEL(G)≤LEL(H)；如果G≺H,则LEL(G)＜LEL(H)。

树的拉普拉斯系数涉及到树的维纳指标、修改超维纳指标、关联能量和Laplacian-like能量。

2 预备知识

对于图G,令μ(G)表示L(G)的最大特征值, dG(v)表示G的顶点v在G中的度。G的1度顶点称为G的悬挂点,G关联于悬挂点的边称为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知结论成立。

连通图G中度大于2的顶点称为G的分枝点,G中顶点u和v之间最短路的长度称为u和v之间的距离。G的顶点v的离心率等于从v到其他所有顶点间距离的最大值。G中具有最小离心率的顶点称为G的中心。树的中心是一个或两个邻接的顶点[2]。

定义2 令v是树T的一个度为m+1的顶点,记v的所有邻接点为u,v1,v2,…,vm。假设H1,H2,…, Hm是关联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关于H1的一个δ变换,T是T′从u到v关于H1的一个δ-1变换。显然,δ变换保持树的悬挂点数不变。

引理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外,假设v的其他邻接点都在悬挂路上并且假设H=vv1v2…vt就是一个在v处的悬挂路。令T″是从T中删除边vu1,然后把v和u1等同得到的树。令T‴是在T″中增加新的悬挂边vtu′1后得到的树。

一个具有唯一分枝点v的树称为关于根v的星状树。如果一个星状树关于根的所有悬挂路都有几乎相等的长度,则称它是平衡星状树。用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。容易发现,D(n,m,r)有n=st+ 2个点,s个悬挂点和直径2t+1。如果d是一个偶数,则记ε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是一个偶数时,T≅S(sd/2+1,s)；d是一个奇数时,存在整数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的所有悬挂点。容易发现,T的所有中心都在Pd+1上。

于是sd≥2(n-1)。由式(2)知sd=2(n-1),当且仅当

这就得到s(d-1)≥2(n-2)。由式(3)知s(d-1)=2(n-2),当且仅当

图1 一个特殊星状树Fig.1 A special starlike tree

引理6如果n,d,s是满足s(d-εd)≥2(n-1-εd)且3≤s≤n-d+1的正整数,则Tn,d,s具有n个顶点,s个悬挂点和直径d。

证明由定义知,Tn,d,s有s个悬挂点,并且它的顶点数等于

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

3 主要结论及其证明

定理3在所有具有n个顶点,s个悬挂点和直径d的树中,Tn,d,s是偏序关系≤下的唯一最小元。

证明由于路Pn和星Sn分别是有2个悬挂点和n-1个悬挂点的唯一树,于是下面假设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的分枝点个数。显然,θ(T)≥1。下面只需证明Tn,d,s≺T即可。

情形1假设θ(T)=1。此时,T是一个星状树。保持Pd+1不变,通过应用π-1变换至少一次,T能被变换成Tn,d,s。由引理2得到Tn,d,s≺T。

情形2假设θ(T)≥2。再划分成两种情形。

情形2.1假设T的所有分枝点都在Pd+1上。选择一个与T的根有最大距离的分枝点v。令w是v在Pd+1上介于v和T的根之间的邻接点,H1是Pd+1上关联于v的悬挂路。通过应用从v到w关于H1的一个δ变换,T能变换成一个具有n个顶点,s个悬挂点和直径d的新的树T1。显然,θ(T1)≤θ(T)。如果θ(T1)≥2,则对T1重复上面过程,直到得到一个树Tr为止,其中θ(Tr)=1。于是得到有n个顶点,s个悬挂点和直径d的树的序列T,T1,T2,…,Tr(r≥1)。因此,由情形1的结论和引理4得到Tn,d,s≤Tr≺…≺T1≺T.

情形2.2假设T至少有一个分枝点不在Pd+1上。令v是不在Pd+1上具有最大深度的一个分枝点,P=vuu′…是从v到T的根的唯一路。由v的假设知,除去u外,v的其他所有邻接点都在长度至少是1的悬挂路上。令H1是关联于v的任意一个悬挂路。通过应用从v到u关于H1的一个δ变换,T能变换成一个有n个顶点、s个悬挂点和直径d的树G1。显然,θ(G1)≤θ(T)。容易发现,u是G1的一个分枝点并且它的深度比v在T中的深度小。如果G1仍然存在分枝点不在Pd+1上,则对G1重复上面过程,直到得到一个树Gm为止,其中Gm的分枝点都在Pd+1上。于是得到有n个顶点,s个悬挂点和直径d的树的序列T,G1,G2,…,Gm(m≥1)。由引理4知 Gm≺…≺G1≺T。既然Gm满足情形2.1的条件,于是由情形2.1的结论得Tn,d,s≤Gm≺T。

推论1在所有具有n个顶点,s个悬挂点和直径d的树中,Tn,d,s是分别具有最小维纳指标、修改超维纳指标和LEL(=IE)的唯一树。

推论2[12]在所有具有n个顶点和s个悬挂点的树中,S(n,s)是偏序关系≤下的唯一最小元。

证明令T≇S(n,s)是任意一个具有n个顶点和s个悬挂点的树,并且记T的直径为d。如果T≇Tn,d,s,则由定理3得

如果Tn,d,s≇S(n,s),则在Tn,d,s的最长悬挂路和最短悬挂路之间反复应用π-1变换,直到所有悬挂路的长度变成几乎相等为止。最后得到的树为S(n,s),于是由引理2知

由式(5)和(6),推论得证。

推论3[11]在所有具有n个顶点和直径d的树中,Tn,d,n-d+1是偏序关系≤下的唯一最小元。

证明令T≇Tn,d,n-d+1是任意一个具有n个顶点和直径为d的树,并且记T的悬挂点数为s。如果T≇Tn,d,s,则由定理3得

令Pd+1是Tn,d,s的一个最长路。如果Tn,d,s≇Tn,d,n-d+1,则对不在Pd+1上的Tn,d,s的悬挂路反复应用π-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)的唯一分枝点。假设P是一个端点为w而另一个端点是悬挂点的最长路,记P的悬挂点为v。令T=S(n,s)-v+wv,则T是一个具有n个顶点和s+1个悬挂点的树。由推论2和引理2得S(n,s+1)≤T≺S(n,s)。

令As,t表示在星图St+1的中心增加s个长为2的悬挂路得到的树。对一个n点树T,令α和α′分别表示T的独立数和匹配数。熟知,α+α′=n。注意到α′≤n/2,于是α≥n/2。

设G=(V,E)是一个简单图,B是V∪E的一个子集。如果B的任两个元素既不邻接,也不关联,则称B为G的一个全独立集。元素个数最多的全独立集称为G的最大全独立集,并且最大全独立集的元素数称为G的全独立数,记为γ。

定理4在所有具有n个顶点和全独立数为γ的树中,An-γ-1,2γ-n+1是偏序关系≤下的唯一最小元。

证明令T≇An-γ-1,2γ-n+1是任意一个具有n个顶点和全独立数为γ的树。记T的悬挂点数为s。既然T的所有悬挂点构成T的一个独立集并且T的独立集一定是T的全独立集,于是s≤α≤γ。注意到α≥n/2,于是γ≥n/2。既然S(n,γ)的所有悬挂路具有几乎相等的长度,于是由γ≥n/2知S(n, γ)的所有悬挂路的长度不超过2。令x和y分别是S(n,γ)中长为2和长为1的悬挂路的个数,则2x+ 1+y=n,x+y=γ。容易发现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个顶点和全独立数为γ的树中,An-γ-1,2γ-n+1是分别具有最小维纳指标、修改超维纳指标和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].华东师范大学学报:自然科学版,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

国家自然科学基金项目(10871204)；中央高校基本科研业务费专项(09CX04003A)

谭尚旺(1965-),男,教授,硕士,研究方向为图论。E-mail:tswang@sina.com。