拉手蜘蛛圖的能量

雷 林, 何常香

(上海理工大學 理學院,上海 200093)

(College of Science,University of Shanghai for Science and Technology,Shanghai 200093,China)

拉手蜘蛛圖的能量

雷 林, 何常香

(上海理工大學 理學院,上海 200093)

圖G的能量定義為其鄰接矩陣的所有特征值的絕對值之和.拉手蜘蛛圖定義為從K2的2個端點分別長出若干條懸掛邊和長為2的懸掛路所得到的圖.用ζn表示點數為n的所有拉手蜘蛛圖構成的集合,通過擬序的方法,研究了拉手蜘蛛圖的能量,并確定了ζn中能量最小的圖.

圖; 能量; 擬序; 蜘蛛圖

1 基本概念及背景介紹

文獻[7]中給出了多項式的擬序定義.

a. 若對所有的0≤i≤n,均有ai≤bi,則記f(x)?g(x);

b. 若f(x)?g(x)且f(x)≠g(x),則記f(x)g(x).

若存在i,j∈{0,1,2,…,n},使得aibj,則稱多項式f(x),g(x)擬序不可比.

當G為二分圖時,G的能量可寫為[7]

定義2[7]令G1和G2為n階的二分圖,

根據能量的積分公式,對于同階的二分圖G1和G2,由G1?G2可得E(G1)≤E(G2),由G1G2可得E(G1)

2 主要引理

圖

引理1[8]令u,v分別為圖G,H的非孤立點(G·H為G與H的粘合),則有

a.φ(G·H,x)=φ(G,x)φ(H-v,x)+φ(G-u,x)φ(H,x)-xφ(G-u,x)φ(H-v,x);

b. 若圖G,H均為二分圖,那么,

若u為二分圖G中的非孤立點,用Gu(t1,t2)表示在u上添加t1條懸掛邊和t2條長為2的懸掛路所得到的圖.

推論1[8]令u為二分圖G中的非孤立點,則

推論2 令u為二分圖G中的非孤立點,則

證明 用H表示恰有1個公共端點的k條長為2的懸掛路所成的圖,記公共點為v,則Gu(0,k)可以看成G和H在點u和v的粘連.

可直接計算出

所以

由引理1可得

推論3 令u為二分圖G中的非孤立點,則

證明 令H=Gu(t1,0),由推論1可得

顯然,Gu(t1,t2)=Hu(0,t2),由推論2可得

引理2[9](移星操作) 若圖G為非平凡連通二分圖,u,v為G上不同的兩點,Gu,v(s,t)表示在u上添加s條懸掛邊,在v上添加t條懸掛邊所得到的圖,令s,t,s′,t′均為非負整數,且s+t=s′+t′.

證明 根據推論2，有

令F=Gu(0,s),則G(u,v|s,t)=Fv(0,t),所以，

那么

由于s+t=s′+t′,s-s′=t′-t,所以,上述計算結果可簡化為

引理4[4](縮邊定理) 對任意的n階樹T,且T至少有1個非懸掛邊,經α操作(如圖2所示)后變為T0,則T?T0且E(T)>E(T0).

圖2 α操作

引理5[10]若v為單圈圖或二分圖的非孤立點,K1表示孤立點,那么,G?(G-v)∪K1.

引理6[10]G,G′為單圈圖或二分圖,u,v,u′,v′分別為G,G′的割邊.

a. 若G-uv?G′-u′v′且G-u-v?G′-u′-v′,則G?G′;

b. 若G-uvG′-u′v′或G-u-vG′-u′-v′,則GG′.

在研究拉手蜘蛛圖的能量時,對于圖3和圖4中的兩類確定圖的能量需單獨比較.

證明a. 當s1+t1=1,s2+t2=1時,

所以

圖3 兩類圖(1)

b. 當s1+t1≠1或s2+t2≠1時,

由引理4(縮邊定理)可得

所以

圖4 兩類圖(2)

證明 由圖4可直接得到

在圖u,v兩點間移長為2的懸掛路,由引理3可得

同上,由引理3可得

綜合式(1)和式(2),利用引理6的結論,即可證明引理8成立.

3 主要結論

由推論2的計算式可得

證明 設s1≥t1.

a. 當s1≥t1,s1-t1+1≥t2-s2時,由引理9可得

反復用引理9,則

b. 當s1≥t1,s1-t1+1

若s1>t1.因為,s1+s2+1s2.

若s2=0,由引理8可得

結論得證.

證明 設s1≥t1,由定理1可得

綜上可得

結論得證.

[1]GUTMANI.Theenergyofagraph:oldandnewresults[M]∥BETTENA,KOHNERTA,LAUER.AlgebraicCombinatoricsandApplications.BerlinHeidelberg:Springer,2001.

[2]GUTMANI,POLANSKYOE.Mathematicsconceptsinorganicchemistry[M].BerlinHeidelberg:Springer-Verlag,1986.

[3]LIXL,SHIYT,GUTMANI.Graphenergy[M].NewYork:Springer,2012.

[4]TIANT,YANWG,LISL.Ontheminimalenergyoftreeswithagivennumberofverticesofodddegree[J].MATCHCommunicationsinMathematicalandinComputerChemistry,2015,73(1):3-10.

[5]RENQIANS,GEYP,HUOBF,etal.Onthetreewithdiameter4andmaximalenergy[J].AppliedMathematicsandComputation,2015,268:364-374.

[6]HECX,WUBF,YUZS.Ontheenergyoftreeswithgivendominationnumber[J].MATCHCommuni-cationsinMathematicalandinComputerChemistry,2010,64(1):169-180.

[7]SHANHY,SHAOJY,ZHANGL,etal.Anewmethodofcomparingtheenergiesofsubdivisionbipartitegraphs[J].MATCHCommunicationsinMathematicalandinComputerChemistry,2012,68(3):721-740.

[8]SHANHY,SHAOJY.Theproofofaconjectureonthecomparisonoftheenergiesoftrees[J].JournalofMathematicalChemistry,2012,50(10):2637-2647.

[9] 夏玲艷.圖的變換對圖的擬序和能量的影響及其應用[D].上海:同濟大學,2015.

[10]SHANHY,SHAOTY,GONGF,etal.Anedgegraftingtheoremontheenergyofunicyclicandbipartitegraphs[J].LinearAlgebraanditsApplications,2010,433(3):547-556.

(編輯:石 瑛)

Energy of the Hand-in-Hand Spider Graph

LEI Lin, HE Changxiang

The energy of a graphGis defined as the sum of absolute values of all eigenvalues of the graph.The hand-in-hand spider graph was obtained fromK2by adding some pendent edges and pendent paths of length 2 at its two end-vertices.The symbolζnwasusedtodenotethesetofhand-in-handspidergraphsofordern.By using the quasi-order of graph,the energy of the hand-in-hand spider graph was studied,and the graphs with the first smallest energies inζnweredetermined.

graph;energy;quasi-order;spidergraph

1007-6735(2017)01-0007-05

10.13255/j.cnki.jusst.2017.01.002

2016-06-12

國家自然科學基金資助項目(11301340,11201303);上海市自然科學基金資助項目(12ZR1420300);滬江基金資助項目(B14005)

雷 林(1992-),女,碩士研究生.研究方向:代數圖論.E-mail:1154375441@qq.com

何常香(1979-),女,副教授.研究方向:代數圖論.E-mail:changxiang-he@163.com

O 157.5

A

(CollegeofScience,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China)