直徑為5的一類樹的擬序

杜輕松，賈亞榮，李亞寧，王志慧，火博豐，2*

(1.青海師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，青海 西寧 810008；2.青海省物聯(lián)網(wǎng)重點實驗室，青海 西寧 810008)

0 引言

一個圖G的能量可以被定義為其鄰接矩陣特征值的絕對值之和[1].研究圖能量的排序有一定的化學(xué)背景.能量概念最早源于人們對共軛碳?xì)浠衔锓肿拥娜喀?電子能量的近似估計.由分子化學(xué)理論，共軛分子的圖能量越大，相對應(yīng)的熱力學(xué)穩(wěn)定性越強(qiáng).近年來，關(guān)于圖能量的研究有很多結(jié)果.對于樹的極值能量，上世紀(jì)70年代Gutman[2]首次得到n個頂點的具有第一、第二極大能量和第一，第二，第三、第四極小能量的樹的結(jié)構(gòu)，其中路Pn和星圖Sn分別是最大能量和最小能量的圖；2008年，李書超等[3]確定了第三大能量樹的結(jié)構(gòu).2010年火博豐等[4]確定了具有第四大能量樹的結(jié)構(gòu).2012年，Andriantiana[5]刻畫了直徑為n-i-1(其中i=1，2，3，4，6，8，10，12，14，16，18)的極大能量樹的結(jié)構(gòu)，對相當(dāng)大的n，確定出了當(dāng)n為奇數(shù)時從第1到第3n-84的極大能量樹和當(dāng)n為偶數(shù)時從第1到3n-87的極大能量樹的結(jié)構(gòu).2005年，晏衛(wèi)根[6]等人確定了給定直徑的具有極小能量的樹的結(jié)構(gòu).關(guān)于給定小直徑的具有極大能量的樹，歐建平[7]確定了中心點的度為且直徑為4的具有極大能量樹的結(jié)構(gòu).索南仁欠[8]等人給出了直徑為3和4的具有極大能量的樹的結(jié)構(gòu).喬小琴等[9]給出了直徑為5的具有極大能量的樹的一個必要條件.在此基礎(chǔ)上，賈亞榮等[10]給出了直徑為5的具有極大能量的樹的結(jié)構(gòu)范圍.本文討論當(dāng)p≥q+2，q=1時，這類直徑為5的樹的懸掛點分配與擬序變化，進(jìn)而與能量變化的關(guān)系.

1 基礎(chǔ)知識

令G是階為n，鄰接矩陣為A(G)的圖，并且令G的特征多項式為φ(G，x)或φ(G).

圖G的特征多項式與它的結(jié)構(gòu)的關(guān)系可以由下面的sachs引理來體現(xiàn).

Lk表示圖G有k個頂點的Sachs子圖的集合，即子圖的每個分支要么是k2，要么是圈；ω(S)與c(S)分別表示在S中的連通分支個數(shù)和包含圈的個數(shù).此外，a0=1.

從Sachs引理容易看出，如果圖G是一個二部圖，那么對于任意k≥0，a2k+1=0.因此

對于圖G的特征多項式，有如下的遞推公式.

引理1.2[1]令uv是圖G的一條邊，則

c(uv)表示包含uv的圈集.特別的，如果uv表示懸掛邊，v表示懸掛點，則

φ(G)=xφ(G-uv)-φ(G-u-v).

從引理1.2明顯看出G是無圈圖時的遞推公式如下.

推論1.1[2]圖G是一個森林且圖G的一條邊e=uv，則圖G的特征多項式為，

φ(G)=φ(G-e)-φ(G-u-v).

關(guān)于圖G的能量有如下定義.

1940年，Coulson[11]獲得了經(jīng)典的Coulson積分公式，它把離散的特征值與如下的連續(xù)函數(shù)的積分聯(lián)系起來：

當(dāng)G1和G2是兩個有相同點頂點的圖，則可直接應(yīng)用得到如下公式：

對于n個頂點圖G的能量，也可表示為

(1)

(2)

從(2)以及對數(shù)函數(shù)和積分的性質(zhì)，他們觀察到擬序和能量大小存在如下關(guān)系：

G1?G2?E(G1)≤E(G2)，

G1G2?E(G1)

這個關(guān)系是能量研究的一個重要工具.

喬小琴[9]等首先定義了如下的一類樹：(1)固定兩個中心點的度分別為s+1和t+1；(2)對度分別為s+1和t+1的兩個中心點，到每個中心點的距離為2的懸掛點的個數(shù)分別固定為a和b.記這樣一個樹的集合為Tn(a，s；b，t)，注意到a+b=n-s-t-2.這相當(dāng)于給直徑為5的n階樹做了一個劃分{Tn(a，s；b，t)|s，t≥1；a，b≥1}.他們發(fā)現(xiàn)在每個圖類Tn(a，s；b，t)中，每一側(cè)的懸掛點分配越均勻，擬序越大.且在每一類圖中具有極大擬序的圖唯一確定，記為T(p，s1，s；q，t1，t)(如圖1)，它除了滿足圖類Tn(a，s；b，t)的條件(1)，(2)之外，還要滿足條件(3)：對于與同一中心點相鄰的任意兩個(非中心)點，與它們分別相鄰的懸掛點的個數(shù)之差不超過1.這里a=(p-1)s+s1，1≤s1≤s，b=(q-1)t+t1，1≤t1≤t.注意到p和s1被a，s唯一確定，q和t1被b，t唯一確定.因此我們可以把Tn(p，s1，s；q，t1，t)簡寫為Ta，s；b，t.

圖1

引理1.3[9]對任意T∈Tn(a，s；b，t)，有TTn(p，s1，s；q，t1，t)=Ta，s；b，t.

引理1.4[10]對圖Tn(p，s1，s；q，t1，t)=G，若p≥q+2，q≥2.

(1)當(dāng)s1>1，t>t1時，Tn(p，s1-1，s；q，t1+1，t)?G；

(2)當(dāng)s1>1，t=t1時，Tn(p，s1-1，s；q+1，1，t)?G；

(3)當(dāng)s1=1，t>t1時，Tn(p-1，s，s；q，t1+1，t)?G；

(4)當(dāng)s1=1，t=t1時，Tn(p-1，s，s；q+1，1，t)?G.

對于p≥3，q=p-1時的情形，賈亞榮等[10]得到類似結(jié)論.

引理1.5[10]令G=Tn(p，s1，s；p-1，t1，t)，t>t1≥1，s>s1≥1，p≥3.

(1)若s1>1，則GTn(p，s1-1，s；p-1，t1+1，t)；

(2)若s1=1，則GTn(p-1，s，s；p-1，t1+1，t).

2 主要定理

定理設(shè)T(p，s1，s；q，t1，t)=G，若p≥q+2，且q=1，s≥s1≥1，t≥t1≥1.

(1)當(dāng)s1>1，t>t1時，Tn(p，s1-1，s；1，t1+1，t)?G；

(2)當(dāng)s1>1，t=t1時，Tn(p，s1-1，s；2，1，t)?G；

(3)當(dāng)s1=1，t>t1時，Tn(p-1，s，s；1，t1+1，t)?G；

(4)當(dāng)s1=1，t=t1時，Tn(p-1，s，s；2，1，t)?G.

證明：(1)設(shè)Tn(p，s1，s；1，t1，t)=G，Tn(p，s1-1，s；1，t1+1，t)=G1；如圖2所示.

圖2

根據(jù)推論1.1的特征多項式的遞歸公式，可以將G和G1的特征多項式按如下方式化簡：

φ(G)=φ(T(p，s1，s))φ(T(1，t1，t))-φ(Sp+1)s1φ(Sp)s-s1φ(S2)t1φ(S1)t-t1

=xt-t1-1φ(K2)φ(Sp+1)s1-1φ(Sp)s-s1-1{x2p-2[x4-(2p+s-1)x2+(p2+sp-p-s1)]

φ(G1)=φ(T(p，s1-1，s))φ(T(1，t1+1，t))-φ(Sp+1)s1-1φ(Sp)s-s1+1φ(S2)t1+1φ(S1)t-t1-1

=xt-t1-2φ(K2)t1φ(Sp+1)s1-2φ(Sp)s-s1{x2p-2·[x4-(2p+s-1)x2+(p2+sp-p-s1+1)]

令H(x)=φ(Sp+1)s1-2φ(Sp)s-s1-1φ(K2)t1-1φ(S1)t-t1-2

f1(x)=x4-(2p+s-1)x2+(p2+sp-p-s1)

f2(x)=x4-(1+t)x2+(t-t1)

g1(x)=f1(x)+1

g2(x)=f2(x)-1

h(x)=(p-1)·(x2-p)·(x2-(p-1))(x2-1)

則

φ(G1)-φ(G)=xt-t1-2φ(K2)t1-1φ(Sp+1)s1-2φ(Sp)s-s1-1{φ(K2)φ(Sp)[x2p-2·[x4-(2p+s-1)x2

+(p2+sp-p-s1)][x4-(1+t)x2+(t-t1)]-(p-1)(x2-p)(x2-(p-1))

(x2-1)]-xφ(Sp+1)[x2p-2·[x4-(2p+s-1)x2+(p2+sp-p-s1)]

[x4-(1+t)x2+(t-t1)]-(p-1)(x2-p)(x2-(p-1))(x2-1)]}

因為s1>1，t>t1，則：

b'0=p-1>0.

b'2=p(2p-3)+s(p-2)+tp+1>0.

b'4=(p-2)(p2+sp-p-s1)+(p-1)(4p+2tp+st+t-t1)+t>0.

b'6=(p-1)((2p+s)(t-t1)+(2p2+1+t1-2p+sp-s)+p(t-t1-1)>0.

b'8=(p-1)(p2+sp-p-s1)(t-t1)+(p-1)(t-t1-1)+p(p-1)2>0.

當(dāng)k=0，1時，(-1)k(b2k(G1)-b2k(G))=0.

(2)設(shè)Tn(p，s1，s；1，t，t)=G，Tn(p，s1-1，s；2，1，t)=G2；如圖3所示.與(1)類似可得

圖3

φ(G)=φ(T(p，s1，s))φ(T(1，t，t))-φ(Sp+1)s1φ(Sp)s-s1φ(K2)t

φ(G2)=φ(T(p，s1-1，s))φ(T(2，1，t))-φ(Sp+1)s1-1φ(Sp)s-s1+1φ(S3)φ(S2)t-1

=φ(Sp+1)s1-2φ(Sp)s-s1φ(K2)t-2{x2p[x4-(2p+s-1)x2+(p2+sp-p-s1+1)]

令H(x)=φ(Sp+1)s1-2φ(Sp)s-s1-1φ(S2)t-2

f1(x)=x4-(2p+s-1)x2+(p2+sp-p-s1)

f2(x)=x2-(1+t)

g1(x)=x4-(2p+s-1)x2+(p2+sp-p-s1+1)

g2(x)=x6-(3+t)x4+(1+2t)x2

h(x)=(p-2)(x2-p)·(x2-(p-1))(x2-1)

則

因為s1>1，t=t1，則

b'0=1-1=0.b'2=-3-t-p+3+p+t=0.

b'4=p-1>0.b'6=(2p+s-1)(p-3)+tp-t+2p-1>0.

b'8=(p-1)(p2+sp-p-s1+t)+(1+2t)+(tp-2t-1)(2p+s-1)+2p(p-2)>0.

b'10=(tp-2t-1)(p2+sp-p-s1)+(p-1)(1+2t)+(p-2)(p2+p-1)>0.

b'12=p(p-1)(p-2)>0.

(3)設(shè)Tn(p，1，s；1，t1，t)=G，Tn(p-1，s，s；1，t1+1，t)=G3；如圖4所示:

圖4

φ(G)=φ(T(p，s1，s))φ(T(1，t，t))-φ(Sp+1)φ(Sp)s-1φ(S2)t1φ(S1)t-t1

=xt-t1-1φ(Sp)s-2φ(K2)t1-1{x2p-2[x4-(2p+s-1)x2+(p2+sp-p-1)]·[x4-(1+t)x2

φ(G3)=φ(T(p-1，s，s))φ(T(1，t1+1，t))-φ(Sp)sφ(S2)t1+1φ(S1)t-t1-1

=xt-t1-2φ(SP)s-1φ(K2)t1{xp-1[x2-(p+s-1)][x4-(1+t)x2+(t-t1-1)x2]-xφ(K2)φ(SP)}

令H(x)=φ(Sp)s-2φ(S2)t1-1φ(S1)t-t1-2

f1(x)=x4-(2p+s-1)x2+(p2+sp-p-1)

f2(x)=x4-(1+t)x2+(t-t1)

g1(x)=x2-(p+s-1)

g2(x)=x4-(1+t)x2+(t-t1-1)x2

h(x)=(p-1)(x2-(p-1))(x2-1)

則

因為s1=1，t>t1，則

b'0=1-1=0.b'2=0.b'4=p-1>0.

b'6=(2p+s-2)(t-t1)+(p-1)(p+s+t+1)-(2p+s)+(1+t)>0.

b'8=8t-3t1+2st-s-1>0.

b'10=(p-1)(p+s-1)(t-t1-1)+(p-1)2>0.

(4)設(shè)Tn(p，1，s；1，t，t)=G，Tn(p-1，s，s；2，1，t)=G4.如圖5所示:

圖5

φ(G)=φ(T(p，1，s))φ(T(1，t，t))-φ(Sp+1)φ(Sp)s-1φ(S2)t

=φ(Sp)s-2φ(K2)t-1{x2p-1[x4-(2p+s-1)x2+(p2+sp-p-1)][x2-(1+t)]

φ(G4)=φ(T(p-1，s，s))φ(T(2，1，t))-φ(Sp)sφ(S3)φ(S2)t-1

令H(x)=φ(Sp)s-2φ(K2)t-2

f1(x)=x4-(2p+s-1)x2+(p2+sp-p-1)

f2(x)=x2-(1+t)

g1(x)=x2-(p+s-1)

g2(x)=x6-(3+t)x4+(1+2t)x2

h(x)=(p-2)(x2-(p-1))(x2-1)

因為s1=1，t=t1，則

b'0=1-1=0.b'2=0.

b'4=p-2>0.b'6=p2-3p+tp-t+sp-3s+2>0.

b'8=p(p-3)(t+1)+s(t(p-2)-1)+t+2>0.

b'10=(p-2)(p-1)>0.