單圈圖永久和的極值

陳蘭，吳廷增

(青海民族大學數(shù)學與統(tǒng)計學院，青海 西寧 810007)

設G是一個有n個頂點的圖。一個Sachs圖是一個簡單，它的每一個組成部分是獨立的邊或圈。設H是有k個頂點的圖。用C(H)表示圖H中圈的數(shù)。G的積和多項式定義為

其中A(G)為G的鄰接矩陣，

圖的積和多項式已被廣泛研究，最近的研究見文獻[1-5]。

圖的永久和，記為PS(G),是指積和多項式π(G,x)的所有系數(shù)的絕對值的和，即

圖的永久和是最近提出的概念。研究表明圖的永久和在化學分子的物理、化學性質(zhì)中表現(xiàn)非常活躍。文獻[6]中發(fā)現(xiàn)了富勒烯C50(D5h)后，文獻[7]中指出了C50(D5h)的永久和在C50中的271個非同構(gòu)的富勒烯中達到最小，并指出永久和與分子圖的穩(wěn)定性密切相關(guān)。近年來,有一些關(guān)于永久和的重要結(jié)果被出版, 文獻[8]確定了關(guān)于永久和的極值六邊形鏈；文獻[9]研究了八邊形鏈永久和的性質(zhì)；文獻[10]刻畫了樹中最大和最小的永久和。

令Un為n階連通單圈圖集合。文獻[10]和[11]分別刻畫了n階連通單圈圖集合Un中最大、最小和次大、次小的永久和。在此結(jié)果的基礎上，本文刻畫了n階連通單圈圖集合Un中第三小直至第七小的永久和及其相應的圖。

1 一些引理

證明主要結(jié)論之前,先列出或證明一些引理。

引理1[10]設T是一個n個頂點的樹，則n≤PS(T)≤F(n+1)。

這里F(n+1)是第n+1個Fibonacci數(shù)，而且左邊等號成立當且僅當T=Sn，右邊等號成立當且僅當T=Pn。

引理3[10]設圖G和H是無公共頂點的圖，則PS(G∪H)=PS(G)PS(H)。

引理4[10]

(i)e=uv是圖G的一條邊，C(e)是包含e的圈的集，則

(ii)設v是圖G的一個頂點，C(v)是包含v的圈的集，則

注1 如果一個圖有個0頂點稱為空圖，記為?，約定PS(?)=1。

引理5[11]設

n≥5，則 3n-4≤PS(G)。

引理6[11]

(i) 當n≥3時，PS(Cn)=F(n+1)+F(n-1)+2；

注2 由公式(ii)立即可得：

(iii)當n≥5且4≤r≤n-1時，PS(G″(r,n-r))=(n-r+1)F(r)+2F(r-1)+2。

注3 由公式(iii)立即可得：

PS(G″(4,n-4))=3n-3，PS(G″(5,n-5))=5n-12，PS(G″(6,n-6))=8n-28

(iv) 當n≥5且1≤s≤n-4時，PS(G′(n,n-3-s,s))=2(ns+n-s2-2s)。

注4 由公式(iv)立即可得：PS(G′(n,n-4,1))=2(2n-3),PS(G′(n,n-5,2))=2(3n-8)。

=[(t1+2)(n-t1-1)+2]-[(t2+2)(n-t2-1)+2]

=[(t1-t2)+2+t2][n-(t1-t2)-t2-1]+[(t1-t2)-2-t1][n+(t1-t2)-t1-1]

=(t1-t2)n-(t1-t2)2-(t1-t2)(t2+1)+(2+t2)n-(2+t2)(t1-t2)-(2+t2)(t2+1)

+(t1-t2)n+(t1-t2)2-(t1-t2)(t1+1)-(2+t1)n-(2+t1)(t1-t2)+(2+t1)(t1+1)

=(t1-t2)[(n-3)-(t1+t2)]≥0

引理8 設4≤r≤n-1,

(i) 當r>4,n>5時，PS(G″(r,n-r))>PS(G″(4,n-4))。

(ii )當r>5,n>6時，PS(G″(r,n-r))>PS(G″(5,n-5))。

證明根據(jù)引理6(iii)，當r>4,n>5時 有

PS(G″(r,n-r))-PS(G″(r-1,n-r+1))

=[(n-r+1)F(r)+2F(r-1)+2]-[(n-r+2)F(r-1)+2F(r-2)+2]

=(n-r+1)F(r)-(n-r)F(r-1)-2F(r-2)=F(r)+(n-r-2)F(r-2)

=(n-r)F(r-2)+F(r-3)>0

所以當r>4,n>5時PS(G″(r,n-r))是r的嚴格增函數(shù)，因此結(jié)論成立。

證明根據(jù)引理6(i)和(ii)，有

=F(n+1)+F(n-1)-(t+2)(n-t-1)

當6≤t≤n-9時，

F(n+1)+F(n-1)

=F(t)F(n-t+2)+F(t-1)F(n-t+1)+F(t)F(n-t)+F(t-1)F(n-t-1)

≥t(n-t+2)+(t-1)(n-t+1)+t(n-t)+(t-1)(n-t-1)

=(4t-2)(n-t-1)+6t-2

所以

≥(4t-2)(n-t-1)+6t-2-(t+2)(n-t-1)

=(3t-4)(n-t-1)+6t-2>0

引理10 當4≤r≤n-1，n≥5時有PS(Cn)>PS(G″(r,n-r))。

證明根據(jù)引理6(i)和(iii)當4≤r≤n-1，n≥5時， 有

PS(Cn)-PS(G″(r,n-r))=[F(n+1)+F(n-1)+2]-[(n-r+1)F(r)+2F(r-1)+2]

=[F(n+1)-(n-r+1)F(r)]+[F(n-1)-2F(r-1)]

下面分三種情況證明：

(i) 當n-r≥3時

F(n+1)=F(n-r+2)F[(n+1)-(n-r+2)+1]+F(n-r+1)F[(n+1)-(n-r+2)]

=F(n-r+2)F(r)+F(n-r+1)F(r-1)

≥(n-r+2)F(r)+F(n-r+1)F(r-1)>(n-r+1)F(r)F(n-1)

=F(3)F[(n-1)-3+1]+F(2)F[(n-1)-3]

=2F(n-3)+F(n-4)≥2F(r)+F(n-4)>2F(r-1)

所以

PS(Cn)-PS(G″(r,n-r))>0，即PS(Cn)>PS(G″(r,n-r))

(ii) 當n-r=2時

PS(Cn)-PS(G″(r,n-r))=F(r+3)-3F(r)+F(r+1)-2F(r-1)

=F(r+3)-F(r)-2F(r+1)+F(r+1)

=F(r+3)-F(r)-F(r+1)=F(r+3)-F(r+2)>0

所以PS(Cn)>PS(G″(r,n-r))；

(iii)當n-r=1時

PS(Cn)-PS(G″(r,n-r))=F(r+2)-2F(r)+F(r)-2F(r-1)

=F(r+2)-2F(r+1)+F(r)

=F(r)-F(r-1)>0

所以PS(Cn)>PS(G″(r,n-r))。

因此 當4≤r≤n-1，n≥5時有PS(Cn)>PS(G″(r,n-r))。

引理11 當n≥7時有PS(Cn)>PS(G′(n,n-4,1))。

證明根據(jù)引理6(i)和(iv)當n≥7時有

PS(Cn)-PS(G′(n,n-r-4,1))=[F(n+1)+F(n-1)+2]-(4n-6)

=F(n)+2F(n-1)-4n+8=3F(n-1)+F(n-2)-4n+8

≥3(n-1)+(n-2)-4n+8=3>0

這里因為n≥7，所以

n-1≥n-2≥5,F(n-1)≥n-1,F(n-2)≥n-2

因此當n≥7時, 有PS(Cn)>PS(G′(n,n-4,1))。

變換1[11]設u是圖G0的一個頂點，圖G1表示把G0的頂點u和樹T一個頂點v用一條邊相連接的圖，圖G2表示把G0的頂點u和星S|T|的中心用一條邊相連接的圖，把從圖G1變換到到圖G2稱為變換1。

引理12[11]設圖G1和圖G2如變換1所定義，則PS(G1)≥PS(G2) 等號成立當且僅當T

是一個星并且v是T的中心。

變換2[11]設圖G2如變換1所定義，用G3表示增加G2中星S|T|的一個懸掛邊并且把星S|T|的中心和G0的頂點u粘在一起的圖，把從圖G2變換到到圖G3稱為變換2。

引理13[11]設圖G2和圖G3如變換1和變換2所定義，則PS(G2)≥PS(G3)，等號成立當且僅當T=K1或u是G0的孤立點。

變換3[11]設G0是一個單圈圖并且Cr=u1u2uru1是G0唯一的圈，設ui和uj是G0的兩個度為2 的頂點，1≤i≤j≤r，用G1表示分別把s≥1個和t≥1個懸掛點連接到圖G0的兩個頂點ui和uj的圖；用G2表示把s+t個懸掛點連接到G0的頂點uj的圖；用G3表示把s+t個懸掛點連接到G0的頂點ui的圖。把從圖G1變換到到圖G2或從圖G1變換到到圖G3稱為變換3。

引理14[11]設圖G1，G2和G3如變換3所定義，則PS(G1)>PS(G2)或PS(G1)>PS(G3)。

2 主要結(jié)論

(i)PS(G)>PS(G″(4,n-4))=3n-3;

(iii)PS(G)>PS(G′(n,n-4,1))=4n-6;

(v)PS(G)>PS(G″(5,n-5))=5n-12。

證明設單圈圖G中唯一圈的圈長為r。下面分三種情況證明：

情形1 當r=n時，則G=Cn。

根據(jù)引理10, 當n≥5時，PS(G)>PS(G″(4,n-4))，PS(G)>PS(G″(5,n-5))；

根據(jù)引理11, 當n≥7時有PS(G)>PS(G′(n,n-4,1))。

因此 當r=n，n≥17時，有下面不等式成立

(i)PS(G)>PS(G″(4,n-4))=3n-3;

(iii)PS(G)>PS(G′(n,n-4,1))=4n-6;

(v)PS(G)>PS(G″(5,n-5))=5n-12。

因此 當4≤r≤n-1，n≥17時，有下面不等式成立

(i)PS(G)>PS(G″(4,n-4))=3n-3;

(iii)PS(G)>PS(G′(n,n-4,1))=4n-6;

(v)PS(G)>PS(G″(5,n-5))=5n-12。

情形3 當r=3時，設C是G中唯一圈長為3的圈。由于n≥17，故C中至少一個頂點的度超過2。

子情形3.1C中至少有兩個頂點的度超過2。因為

因此 當r=3，n≥17且G中唯一圈C中至少兩個頂點的度超過2時，有下面不等式成立

(i)PS(G)>PS(G″(4,n-4))=3n-3;

(iii)PS(G)>PS(G′(n,n-4,1))=4n-6;

(v)PS(G)>PS(G″(5,n-5))=5n-12。

根據(jù)引理6(iv)和注4有PS(G′(n,n-3-s,s))-PS(G′(n,n-5,2))=2(ns+n-s2-2s)-2(3n-8)=2(s-2)(n-s-4)≥0,上式當s≥2，且n-s-3≥1時成立，等號成立當且僅當s=2或n-s-3=1。所以當s≥2且n>7時有PS(G′(n,n-3-s,s))≥PS(G′(n,n-5,2))。

又根據(jù)引理6(ii)注2，(iii)注3和(iv)注4，顯然當n≥17時有

PS(G′(n,n-5,2))>PS(G″(5,n-5))

因此 當r=3，n≥17且G中唯一圈C中只有一個頂點的度超過2時，有下面不等式成立

(i)PS(G)>PS(G″(4,n-4))=3n-3;

(iii)PS(G)>PS(G′(n,n-4,1))=4n-6;

(v)PS(G)>PS(G″(5,n-5))=5n-12。

綜合上面三種情形：當G是一個單圈圖，并且n≥17，

(i)PS(G)>PS(G″(4,n-4))=3n-3;

(iii)PS(G)>PS(G′(n,n-4,1))=4n-6;

(v)PS(G)>PS(G″(5,n-5))=5n-12。

定理1證畢。

定理2 設G是一個n(n≥17)個頂點的單圈圖。

證明根據(jù)引理6(ii)注2、(iii)注3和(iv)注4，顯然當n≥17時，有3n-3<4n-10<4n-6<5n-18<5n-12成立，所以當n≥17時，有下面不等式成立

備注根據(jù)引理6、引理12、引理13和引理14容易得單圈圖頂點數(shù)分別是n=8,9,10,,16時單圈圖永久和第三小到第七小的圖如下所示：

(i) 當n=8時，第三小到第七小永久和的圖分別是：

G′(8,4,1)，G″(5，3)和G′(8,3,2)。

(ii) 當n=9時，第三小到第七小永久和的圖分別是;

G′(9，5,1)和G″(5,4)。

(iii) 當n=10時，第三小到第七小永久和的圖分別是:

G′(10，6,1)和G″(5,5)。

(iv) 當n=11時，第三小到第七小永久和的圖分別是:

和G″(5,6)。

(v) 當n=12時，第三小到第七小永久和的圖分別是:

和G″(5,7)。

(vi) 當n=13時，第三小到第七小永久和的圖分別是：

(vii) 當n=14時，第三小到第七小永久和的圖分別是：

(viii) 當n=15時，第三小到第七小永久和的圖分別是：

(ix) 當n=16時，第三小到第七小永久和的圖分別是：