關(guān)于具有給定二分類的單圈二部圖的極小能量

楊 勇

(佛山科學(xué)技術(shù)學(xué)院信息科學(xué)與數(shù)學(xué)系，廣東佛山528000)

設(shè)G是一個(gè)n階簡(jiǎn)單圖，A(G)是G的鄰接矩陣，I是n階單位陣，G的特征多項(xiàng)式φ(G)=det(λIA(G))．設(shè) G 的特征值為λ1，λ2，…，λn，則 G 的能量定義為［1］

在理論化學(xué)中，共軛分子的π-電子總能量可通過(guò)其分子圖近似計(jì)算，關(guān)于分子圖的能量已有許多結(jié)果［1-4］．

當(dāng)G是一個(gè)n階二部圖時(shí)，則［5］

其中 bi(G)≥0，0≤i≤?n/2」．于是，Sachs定理［5］表述為對(duì)于任意 1≤i≤?n/2」，有

其中L2i是G的2i階Sachs子圖集(Sachs子圖是指每個(gè)分支要么是圈圖，要么是2階完全圖的圖)，p(S)是子圖S的分支個(gè)數(shù)，c(S)是子圖S中圈圖個(gè)數(shù)．另外，規(guī)定b0(G)=1．顯然 b1(G)等于G的邊數(shù)．為了敘述方便，令bi(G)=0，如果i＜0或者i＞?n/2」．眾所周知，E(G)可表示成下列Coulson積分形式［4］

二部圖中的擬序關(guān)系“?”和“?”如下定義:設(shè)G1和G2都是二部圖．如果對(duì)于任意1≤i≤?n/2」，都有 bi(G1)≥bi(G2)，則稱 G1?G2．如果 G1?G2，并且存在某個(gè)k使得bk(G1)＞bk(G2)，則稱G1?G2．由式(1)，E有下面的增屬性:

因此，依據(jù)能量，二部圖的排序可通過(guò)它們的特征多項(xiàng)式系數(shù)確定．

設(shè)G是一個(gè)連通二部圖，則它的頂點(diǎn)集能唯一地劃分成2個(gè)子集V1和V2，使得它的每條邊的2個(gè)端點(diǎn)分別在V1和V2中，(V1，V2)稱為G的二分類．進(jìn)一步地，則稱G是二分類(p，q)的．具有n(≥3)個(gè)頂點(diǎn)n條邊的連通圖稱為單圈圖．

GUTMAN［6］開始在給定的一類圖中研究確定具有最小能量和最大能量的圖，更多結(jié)果參看文獻(xiàn)［7］-［8］．當(dāng) p=2 或 p≥4 時(shí)，LI和 ZHOU［9］確定了給定二分類(p，n-p)的單圈二部圖中具有最小能量的圖，其中p≤?n/2」;當(dāng)p=3時(shí)，他們指出圖B1n或B2n(圖1)具有最小能量．下面將對(duì)p=3的情形做進(jìn)一步的探討．

1 預(yù)備知識(shí)

若uv是G的一條割邊，則由文獻(xiàn)［1］，有φ(G)=φ(G-uv)-φ(G-u-v)，從而有

引理1 設(shè)G是一個(gè)二部圖．若uv是G的一條割邊，則

特別是，若u是G的一個(gè)懸掛點(diǎn)，而v是其唯一的相鄰頂點(diǎn)，則

圖1 圖 Bkn(k=1，2，…，5)Figure 1 Graphs Bkn(k=1，2，…，5)

由引理1，得

引理2 設(shè)G是一個(gè)二部圖．若H是從G中刪除至少一條割邊所得到的生成子圖，則G?H．

引理3 設(shè)G，G'都是二部圖，u(相應(yīng)有u')是G(相應(yīng)有G')的一個(gè)懸掛點(diǎn)，v(相應(yīng)有v')是其唯一的相鄰頂點(diǎn)．若G-u?G'-u'且G-u-v?G'-u'-v'，或者 G-u?G'-u'且 G-u-v?G'-u'-v'，則G?G'．

2 主要結(jié)果

對(duì)于圖G和H，若G與H不同構(gòu)，記為G≠H．設(shè)Pn和Cn分別是n階路圖和圈圖．

圖2 圖Figure 2 Graphs

引理 4［9］設(shè) G)且 G≠B1n，B2n，其中 n≥7，則 G?B2n．

(i)若 G≠B17，B27，B37，則 G?B37．

(ii)若 G≠B17，B27，B37，B47，B57，則 G?B47．

證明 容易看出，給定二分類(3，4)的任何一個(gè)7階單圈二部圖一定同構(gòu)于下列圖之一:圖Bk7和Hi(k=1，2，…，5;i=1，2，3)，其中 H1是在一個(gè)四角形的某個(gè)頂點(diǎn)上加一條長(zhǎng)為3的路所得到的圖，H2是在一個(gè)四角形的2個(gè)相鄰頂點(diǎn)上分別加一條懸掛邊和一條長(zhǎng)為2的路所得到的圖，H3是在一個(gè)六角形的某個(gè)頂點(diǎn)上加一條懸掛邊所得到的圖．由Sachs定理，得

因此，引理結(jié)論成立．

用Sn表示n階星圖，Yn表示在星圖Sn-1的某個(gè)懸掛點(diǎn)上加一條懸掛邊所得到的n階樹圖．頂點(diǎn)不相交的圖 G1，G2，…，Gl的并，記為 G1∪G2∪…∪Gl，特別是，當(dāng) Gj=G(j=1，2，…，l)時(shí)，記為 lG．

證明 對(duì)n用數(shù)學(xué)歸納法．當(dāng)n=7時(shí)，由引理5(i)，結(jié)論顯然成立．假設(shè)當(dāng)n≥8時(shí)，結(jié)論對(duì)n-1階圖成立．設(shè))．注意到G一定是圖2中的3種圖之一．

情形1 G=B1r1，s1，t1．由于 r1+s1+t1=n-6，0≤r1≤s1≤t1，n≥8，故 t1≥1．顯然，G-w1G-w1-z是無(wú)圈圖且包含一條路P5，以及G-w1≠．由歸納假設(shè)，得 G-w1?=B3n-u'，其中u'是B3n的一懸掛點(diǎn)，且它唯一的鄰點(diǎn)v'是非2度頂點(diǎn)．由引理2知G-w1-z?(n-7)P1∪P5?(n-7)P1∪P2∪P3=B3n-u'-v'．因此，由引理 3，得 G?B3n．

情形2 G=B2r2，s2，t2．設(shè) r2≥1，則 s2≥1，G-v1(n-1)，G-v1≠，以及 G-v1-y是無(wú)圈圖且包含一顆樹Y5．由歸納假設(shè)，得G-v1?B3n-1，而由引理 2，又有 G-v1-y?(n-7)P1∪Y5?(n-7)P1∪P2∪P3．因此，由引理 3，得 G?B3n．

設(shè) r2=0．由于 G≠B1n，B2n且 n≥8，故 s2，t2≥1，max{s2，t2}≥2．若 s2≥t2，則 s2≥2，G-v11)，G-v1≠，以及G-v1-y是無(wú)圈圖且包含一條路P5，于是類似情形1的討論，有G?B3n．若 t2≥s2，則 t2≥2，G-w1)，G-w1≠，以及G-w1-z包含一個(gè)子圖P45．由歸納假設(shè)，G-w1?B3n-1，而由引理2，知 G-w1-z?(n-7)P1∪P45．由于 b1(P45)=5 ＞3=b1(P2∪P3)且 b2(P45)=b2(P2∪P3)=2，故 P45?P2∪P3．因此，G-w1-z?(n-7)P1∪P2∪P3，由引理 3，知 G?B3n．

情形3 G=B3r3，s3，t3．若 r3≥1，則 G-u11)，G-u1≠，以及G-u1-x是無(wú)圈圖且包含一顆樹Y5．由歸納假設(shè)，得G-u1?B3n-1，而由引理 2，又有 G-u1-x?(n-7)P1∪Y5?(n-7)P1∪P2∪P3．因此，由引理3，得 G?B3n．

設(shè) r3=0．由于 G≠B3n，故 t3≥1，G-w11)，G-w1≠B1n-1，B2n-1，以及G-w1-z包含一個(gè)子圖P45，于是類似以上的討論，得G?B3n． □

證明 對(duì)n用數(shù)學(xué)歸納法．當(dāng)n=7時(shí)，由引理5(ii)，結(jié)論顯然成立．假設(shè)當(dāng)n≥8時(shí)，結(jié)論對(duì)n-1

情形1 G=B1r1，s1，t1．由于 r1+s1+t1=n-6，0≤r1≤s1≤t1，n≥8，故 t1≥1．顯然 G-w1(n-1)，G-w1≠Bkn-1(k=1，2，…，5)，以及 G-w1-z是無(wú)圈圖且包含一條路P5．由歸納假設(shè)，得G-w1?B4n-u'，其中u'是B4n的一懸掛點(diǎn)，且它唯一的鄰點(diǎn)v'是非2度頂點(diǎn)．由引理2有G-w1-z?(n-7)P1∪P5．顯然 P5?Y5．因此，G-w1-z?(n-7)P1∪Y5=B4n-u'-v'，于是由引理 3，得 G?B4n．

情形2 G=B2r2，s2，t2．設(shè) r2≥1，則 s2≥1．若 G=)=8 ＞6=b3(B49)，b4()=b4(B49)=0，于是 G?B49．設(shè)G≠B22，2，0．顯然 G-v1，G-v1≠Bkn-1(k=1，2，…，5)，以及 G-v1-y是無(wú)圈圖且包含一顆樹Y5．由歸納假設(shè)，得 G-v1?B4n-1，而由引理 2，得G-v1-y?(n-7)P1∪Y5．因此，由引理 3，得 G?B4n．

設(shè) r2=0．由于 G≠B1n，B2n且 n≥8，故 s2，t2≥1，max{s2，t2}≥2．若 s2≥t2，則 s2≥2，G-v1(n-1)，G-v1≠Bkn-1(k=1，2，…，5)，以及 G-v1-y 是無(wú)圈圖且包含一條路P5，于是類似情形1的討論，得 G?B4n．若 t2≥s2，則 t2≥2，G-w1(n-1)，G-w1≠Bkn-1(k=1，2，…，5)，以及 G-w1-z包含一個(gè)子圖P45．由歸納假設(shè)，得G-w1?B4n-1，而由引理2，又得 G-w1-z?(n-7)P1∪P45．由于 b1(P45)=5 ＞4=b1(Y5)，b2(P45)=2=b2(Y5)，故 P45?Y5．因此，G-w1-z?(n-7)P1∪Y5，于是由引理3，得 G?B4n．

情形3 G=B3r3，s3，t3．若 t3≥2，則 G-w1(n-1)，G-w1≠Bkn-1(k=1，2，…，5)，以及 G-w1-z包含一個(gè)子圖P45，于是類似以上的討論，得G?B4n．

設(shè) t3=1．由于 n≥8，故 r3≥1 或 s3≥1．若 r3≥s3，則 r3≥1，G-u1≠Bkn-1(k=1，2，…，5)，以及 G-u1-x是無(wú)圈圖且包含一顆樹 Y5，于是 G?B4n．若s3≥r3，則 s3≥1，G-v1(n-1)，G-v1≠Bkn-1(k=1，2，…，5)，以及 G-v1-y 是無(wú)圈圖且包含一個(gè)子圖P3∪P3．由歸納假設(shè)，得G-v1?B4n-1，而由引理2，又得 G-v1-y?(n-8)P1∪P3∪P3．由于 b1(P3∪P3)=4 和 b2(P3∪P3)=4，故 P3∪P3?P1∪Y5．因此，G-v1-y?(n-7)P1∪Y5，于是由引理 3，得G?B4n．

設(shè) t3=0．因?yàn)?G≠B3n，B4n，所以 r3，s3≥1．顯然(n-1)，G-v1≠Bkn-1(k=1，2，3，5)，以及G-v1-y是無(wú)圈圖且包含一個(gè)子圖S4∪P2．由歸納假設(shè)，得G-v1?B4n-1，而由引理 2，又得 G-v1-y?(n-8)P1∪S4∪P2．因?yàn)?b1(S4∪P2)=4，b2(S4∪P2)=3，所以 S4∪P2?P1∪Y5．因此，G-v1-y?(n-7)P1∪Y5，于是由引理 3，得 G?B4n． □

下述引理8是文獻(xiàn)［9］的猜想，這里將給出嚴(yán)格的證明．

引理8 對(duì)于n≥7，有E(B1n)＜E(B2n)．

證明 由Sachs定理，有

容易看出，若要E1＜E2成立，只需4n-18＜3n-13+，也即E2＞．由文獻(xiàn)［2］知對(duì)于任意一個(gè)沒有孤立頂點(diǎn)的n階圖G，有E(G)≥2故E2＞成立．

由引理4、引理6～引理8和式(2)，有

定理1 設(shè)n≥7，則

(i)圖 B1n，B2n和 B3n分別是(n)中唯一具有最小、第二小和第三小能量的圖．

(ii)圖 B4n是(n)B5n中唯一具有第四小能量的圖．

由Sachs定理，有φ(B5n)=λn-nλn-2+(4n-19)λn-4-(2n-11)λn-6．從上述特征多項(xiàng)式的λn-4和λn-6的系數(shù)，容易看出擬序關(guān)系“?”不能用于比較圖B4n和B5n的能量．

［1］GUTMAN I．The energy of a graph［J］．Ber Math-Statist Sekt Forsc hungszentrum Graz，1978，103:1-22．

［2］GUTMAN I．The energy of a graph:Old and new results［M］∥BETTEN A，KOHNERT A，LAUE R，et al．Algebraic Combinatorics and Applications．Berlin:Springer-Verlag，2001:196-211．

［3］GUTMAN I．Topology and stability of conjugated hydrocarbons:The dependence of totalπ-electron energy on molecular topology［J］．JSerb Chem Soc，2005，70:441-456．

［4］GUTMAN I，POLANSKY O E．Mathematical concepts in organic chemistry［M］．Berlin:Springer-Verlag，1986．

［5］CVETKOVI'C D，DOOB M，SACHSH．Spectra of graphs-theory and application［M］．Heidelberg:Johann Ambrosius Barth，1995．

［6］GUTMAN I．Acyclic system with extremal Hückelπ -electron energy［J］．The oret Chim Acta，1977，45:79-87．

［7］HOU Y．Unicyclic graphs with minimal energy［J］．J Math Chem，2001，29:163-168．

［8］RADA J，TINEO A．Polygonal chains with minimal energy［J］．Lin Algebra Appl，2003，372:333-344．

［9］LI F，ZHOU B．Minimal energy of bipartite unicyclic graphs of a given bipartition［J］．MATCH Commun Math Comput Chem，2005，54:379-388．