宋玲,劉合超,湯自凱

(湖南師范大學 數學與統(tǒng)計學院,湖南 長沙,410081)

拓撲指數是對分子結構進行數值建模的一種方法,它是通過對特征分子圖的矩陣進行一些數字運算而獲得的,特征圖譜是圖的不變量,該圖直接在分子結構中生成并反映出該化合物的結構特征。

WIENER[2]介紹了第一個拓撲指數即圖G的維納指數W(G),定義如下:

HOSOYA[3]提出一種表征飽和烴異構體性質的指數，并且研究了它與維納指數的關系。SKOROBOGATOV和DOBRYNIN[4]定義了n個頂點的圖的平均離心率為

FARAHANI[5]研究了苯環(huán)系統(tǒng)的離心率總和指數,定義如下:

維納指數和離心率總和指數都是基于距離有關的指數問題。關于維納指數，人們對各種給定條件的極值問題進行了研究[6-11]。關于離心率總和指數,FATHALIKHANI等[12]研究了離心率總和指數關于圖形運算的值的相關問題；DE等[13]研究了合成圖的離心率總和指數；SMITH等[14]確定了給定度序列的離心率總和指數的最小化和最大化樹的結構；有關離心率的相關其他問題可以參考文獻[15-18]。在圖論的各種圖形結構中,極大外平面圖是一種特殊的圖形,由于它具有一些特殊結構以及一些非常好的性質,因而引起了許多學者對其進行研究。人們關于極大外平面圖的研究一開始大多數主要集中在染色問題等方面。最近,許多人對極大外平面圖的一些指數問題進行了研究。HOU等[19]研究了n個頂點的極大外平面圖的M1,M2指數上下界并且刻畫出了相應的極值圖。SU等[20]研究了n個頂點的極大外平面圖的一般零階Randic指數上下界并且刻畫了相應的極值圖。目前，也有學者研究了給定n個頂點的極大外平面圖的維納指數的上下界問題。

本文研究了極大外平面圖的離心率總和指數ξ(G),給出了n個頂點極大外平面圖的最小值和最大值并且確定了相應的極值圖。在證明中,首先給出了n個頂點的極大外平面圖的最小值,并且定義了一種新的圖類,接著利用圖形變化克服了“最大值中僅僅靠數學歸納法中不能實現”的問題,最后確定了n個頂點的極大外平面圖中離心率總和指數的最大值，并且確定了當n為偶數時的最大值在新的圖類中達到。

1 預備結論

1)在G中存在1個2度頂點u并且N(u)={v,w}；

2)對于任意1點x∈V(G){v,w},vx∈E(G)和wx∈E(G)至少有1個是成立的。

當n=3,4和5時,極大外平面圖是唯一的。當n=6時,此時存在3個非同構圖(見圖1)；當n=7時,此時存在4個非同構圖(見圖2)；當n=8時,此時存在12個非同構圖(見圖3)。并且隨著n的增加,非同構圖的數目也增加。

圖1 頂點數為6時的所有的非同構極大外平面圖Fig.1 All non-isomorphic 6-vertex maximal outerplanar graphs

圖2 頂點數為7時的所有的非同構極大外平面圖Fig.2 All non-isomorphic 7-vertex maximal outerplanar graphs

圖3 頂點數為8時的所有的非同構極大外平面圖Fig.3 All non-isomorphic 8-vertex maximal outerplanar graphs

圖4 圖

在文獻[19]中,HOU等給出了極大外平面圖的一些性質。

引理1[19]令G為n≥4的1個極大外平面圖。若v為G中1個度為2的點,并且其鄰點為u和w,則uw∈E(G)且|N(u)∩N(w)|=2。

1)G中存在1個點u，滿足d(u)=2且N(u)={v,w},d(u)+d(w)=7；

圖5 圖

根據極大外平面圖的定義,可以得到下述事實。

1)若n=6,左邊等式取等時當且僅當G?K1∨P5或者G?H′2(見圖1)；

2)若n≥7,左邊等式取等時當且僅當G?K1∨Pn-1；

通過直接的計算,可以得到下面的兩個結果。

引理3令G為頂點數為n的1個極大外平面圖,其中n≥6,則

ξ(K1∨Pn-1)=2n-1,

引理4令G為頂點數為n的一個極大外平面圖,其中n≥6。

2 極大外平面圖的離心率總和指數的最值

定理1令G為1個頂點數n≥6的極大外平面圖,則ξ(G)≥2n-1等號取等時當且僅當G?K1∨Pn-1。

證明當n=6,H6={H′1,H′2,H′3}(見圖1),通過直接運算,可以得到:

ξ(H′1)=11,ξ(H′2)=12,ξ(H′3)=14

這個結論對于n=6時成立。

接著證明當n≥7時也成立。假設這個結果對于階數小于n的所有的極大外平面圖是成立的。設G為1個極大外平面圖,并且|V(G)|=n。根據引理1,知道G中一定存在1個頂點u且d(u)=2,N(u)={v,w}。令G′=G-u,那么可以得到G′是1個極大外平面圖,并且|V(G′)|=n-1。根據數學歸納法可以得到

ξ(G′)≥2(n-1)-1=2n-3。

由事實1可以得到對于任意的vi∈V(G)有ε(vi)≥2成立。令G′=G-u,得到εG(vi)-εG′(vi)≥0。則

令G為1個階數為n的極大外平面圖,u為1個2度頂點且N(u)={v,w}。由引理2,可以得到d(v)+d(w)≥7。

引理5令G為1個階數為n的極大外平面圖,u為1個2度頂點且N(u)={v,w}。令X為1個頂點子集,

X={x∈V(G){u,v,w}|ε(x)=d(x,u)>d(x,ui)對于任意ui∈V(G){u}}。

若d(v)+d(w)=k,Xk={X|d(v)+d(w)=k}且f(k)=|Xk|,其中k≥9,則可以得到f(7)≥f(k-1)≥f(k)。

證明將用圖形變換來證明。令圖G為1個極大外平面圖(見圖6),xi1xi2(1≤i≤a)為1條弦或者為三角形△xi1vxi2(簡寫為△i)的1條邊,其中a表示以v(而不是w)作為其中1個頂點的三角形的數目?？梢钥吹疆攁≥2時,xi-1,2=xi1,i∈{2,3,4,…,a}是可能成立的。每一個三角形△i都對應著1個外邊界為xi1xi2∪Qi的1個極大外平面圖Gi,其中Qi是外邊界上端點為xi1和xi2的1條路。G-{u,w}即Gi=G[V(Qi)],其中1≤i≤a。類似地,在G中有b個以w(而不是v)作為其中1個頂點的三角形,可以看出b≥0。用△yj1wyj2(簡寫為△′j)表示圖G中邊yj1yj2為弦的三角形?？梢钥闯霎攂≥2時,yj-1,2=yj1,j∈{2,3,4,…,b}是可能的。每一個三角形△′j都對應著1個外邊界為yj1yj2∪Q′j的極大外平面圖G′j,其中Q′j為外邊界上端點為yj1和yj2的1條路。即G′j=G[V(Q′j)]。當a=b=0時,對于任意1個頂點x∈V(G){v,w},vx∈E(G)和wx∈E(G)中至少有1個是成立的。用ki=|V(Qi)|-2≥1表示Qi(1≤i≤a)中既不與v相鄰也不與w相鄰的頂點數目,其中a≥1。類似地,當b≥1時,用lj=|V(Q′j)|-2≥1表示Q′j(1≤j≤b)中既不與v相鄰也不與w相鄰的頂點數目。設z0=N0(v)-N0(w),其中N0(v)=N(v)-{u},N0(w)=N(w)-{u}。由于v和w的對稱性,下面僅證明三角形△xi1vxi2(其中1≤i≤a)的這種情況。

圖6 變換ⅠFig.6 Transformation Ⅰ

變換Ⅰ假設在極大外平面圖G中有2個三角形△xi1vxi2和△xi+1,1vxi+1,2(其中xi2=xi+1,1,i=2,3,4…,a)。令G′=G-vxi2+xi1xi+1,2(見圖6)為通過在G中刪除邊vxi2再添加邊xi1xi+1,2后得到的圖，則G′也是1個階數為n的極大外平面圖。若在G中d(v)+d(w)=k，則dG′(v)+dG′(w)=k-1。接著證明當k≥9時,f(k-1)≥f(k)。下面分別比較G和G′中u和其他頂點的距離。

設Ai={ai∈V(Gi)|d(ai,xi1)≤d(ai,xi2)},Bi={bi∈V(Gi)|d(bi,xi1)>d(bi,xi2)}，

X(Ai)={x∈Ai|x∈X},X(Bi)={x∈Bi|x∈X}。

若ai∈Ai,則dG′(ai,u)=dG(ai,u)，dG′(ai,bi+1)=dG(ai,bi+1)-1，其中，bi+1∈Bi+1；dG′(ai,ai+2)=dG(ai,ai+2)-1。對于vi∈V(G){u,bi+1,ai+2},有dG′(ai,vi)=dG(ai,vi)。若在G中存在點ai0∈X，則在G′中一定有ai0∈X。若在G中ai0?X,則在G′中可能有ai0∈X。綜上可以得到|X(Ai)G′|≥|X(Ai)G|。

若bi∈Bi,則dG′(bi,u)=dG(bi,u)+1，dG′(bi,bi+l)=dG(bi,bi+l)+1,其中，l≥3；dG′(bi,ai+m)=dG(bi,ai+m)+1,其中m≥4；dG′(bi,bi-l′)=dG(bi,bi-l′)+1,其中，l′≥3；

dG′(bi,ai-m′)=dG(bi,ai-m′)+1,其中m′≥2。對于

vi∈V(G){u,bi+l(l≥3),ai+m(m≥4),bi-l′(l′≥3),ai-m′(m′≥2)},

有dG′(ai,vi)=dG(ai,vi)。所以，|X(Bi)G′|≥|X(Bi)G|。

根據Ai和Bi+1,Bi和Ai+1的對稱性,有|X(Bi+1)G′|≥|X(Bi+1)G|,|X(Ai+1)G′|≥|X(Ai+1)G|。

若ai+2∈Ai+2,則dG′(ai+2,u)=dG(ai+2,u)，dG′(ai+2,ai)=dG(ai+2,ai)-1，dG′(ai+2,bi-1)=dG(ai+2,bi-1)-1。對于vi∈V(G){u,ai,bi-1},有

dG′(ai+2,vi)=dG(ai+2,vi)。

所以，|X(Ai+2)G′|≥|X(Ai+2)G|。

根據Ai+2和Bi-1的對稱性,有|X(Bi-1)G′|≥|X(Bi-1)G|。

若bi+2∈Bi+2,則dG′(bi+2,u)=dG(bi+2,u)。對于vi∈V(G){u},有

dG′(bi+2,vi)=dG(bi+2,vi)。

所以，|X(Bi+2)G′|=|X(Bi+2)G|。

同理可得

|X(Ai-1)G′|=|X(Ai-1)G|,|X(Bi-2)G′|=|X(Bi-2)G|,|X(Ai+3)G′|=|X(Ai+3)G|。

若bi+3∈Bi+3,則

dG′(bi+3,u)=dG(bi+3,u)；dG′(bi+3,bi)=dG(bi+3,bi)+1；

dG′(bi+3,ai+1)=dG(bi+3,ai+1)+1；對于vi∈V(G){u,bi,ai+1},可以得到

dG′(bi+3,vi)=dG(bi+3,vi)。

注意dG(bi+3,bi)=dG(bi+3,vi)+dG(v,bi),dG(bi+3,u)=dG(bi+3,v)+1,其中，dG(v,bi)≥1,有dG(bi+3,bi)≥dG(bi+3,u),所以，在G中，bi+3?X?？梢缘玫絛G′(bi+3,bi)=dG(bi+3,bi)+1>dG′(bi+3,u)；在G′中，bi+3?X。同理,有dG(bi+3,ai+1)≥dG(bi+3,u),dG′(bi+3,ai+1)>dG′(bi+3,u)。綜上可知，|X(Bi+3)G′|=|X(Bi+3)G|。

根據Ai-2和Bi+3的對稱性,有|X(Ai-2)G′|=|X(Ai-2)G|。

若ci+l∈Gi+l,其中l(wèi)≥4,則dG′(ci+l,u)=dG(ci+l,u)；dG′(ci+l,bi)=dG(ci+l,bi)+1；dG′(ci+l,ai+1)=dG(ci+l,ai+1)+1。對于vi∈V(G){u,bi,ai+1},有

dG′(ci+l,vi)=dG(ci+l,vi)。

注意dG(ci+l,bi)≥dG(ci+l,u),dG′(ci+l,bi)>dG′(ci+l,u)；dG(ci+l,ai+1)≥dG(ci+l,u),dG′(ci+l,ai+1)>dG′(ci+l,u)。

所以，可得|X(Gi+l)G′|=|X(Gi+l)G|。

根據Gi-l′和Gi+l的對稱性,其中l(wèi)′≥3,有|X(Gi-l′)G′|=|X(Gi-l′)G|。

綜上,可以得到|XG′|≥|XG|,即f(k-1)≥f(k)，其中，k≥9。

變換Ⅱ令Gn=Gn-1-vz0-wz0+x11x12+vx12(見圖7)為通過在Gn-1中刪除邊vz0,wz0然后添加邊x11x12,vx12后所得到的圖。則Gn為1個極大外平面圖,且d(v)+d(w)=7。令

圖7 變換Ⅱ中的圖Gn-1,GnFig.7 GraphGn-1,Gnof Transformation Ⅱ

A1={a1∈V(G1)|d(a1,x11)≤d(a1,z0)},B1={b1∈V(G1)|d(b1,x11)>d(b1,z0)}

A2={a2∈V(G2)|d(a2,z0)≤d(a2,x12)},B2={b2∈V(G2)|d(b2,z0)>d(b2,x12)}

現在比較Gn-1和Gn中點u和其他點的距離。

若a1∈A1,則dGn(a1,u)=dGn-1(a1,u)；dGn(a1,b2)=dGn-1(a1,b2)-1。

對于vi∈V(G){u,b2},有dGn(a1,vi)=dGn-1(a1,vi)。所以，可以得到

|X(A1)Gn|≥|X(A1)Gn-1|。

根據B2和A1的對稱性,有|X(B2)Gn|≥|X(B2)Gn-1|。

若b1∈B1,則

dGn(b1,u)=dGn-1(b1,u)+1；dGn(b1,v)=dGn-1(b1,v)+1；dGn(b1,w)=dGn-1(b1,w)+1。

對于vi∈V(G){u,v,w},有dGn(b1,vi)=dGn-1(b1,vi)。所以，可以得

|X(B1)Gn|≥|X(B1)Gn-1|。

根據B1和A2的對稱性,有|X(A2)Gn|≥|X(A2)Gn-1|

綜上,可以得到|XGn|≥|XGn-1|,且|XGn|≥|XGn-1|≥|XG|,其中在Gn中有d(v)+d(w)=7,則f(7)≥f(k-1)≥f(k),其中k≥9。引理5得證。

定理2令G為頂點數n≥6的1個極大外平面圖,則

證明(1)首先考慮n為奇數的情況。

若n=7,則H7={H″1,H″2,H″3,H″4}(見圖2),根據直接計算,可以得到

ξ(H″1)=13,ξ(H″2)=17,ξ(H″3)=16,ξ(H″4)=18。

所以，當n=7時結論成立。

令V1={v∈V(G){u1,u2}|ε(v)=d(v,u1)>d(v,u)或ε(v)=d(v,u2)>d(v,u),u∈V(G){u1,u2}}則對于vi∈V1,有ε(vi)-εG′(vi)=1。對于vi?V1,有ε(vi)=εG′(vi)。因此可得

綜上,當n=2k+1時,有

(2)若n=6,則H6={H′1,H′2,H′3}(見圖1),根據直接的計算,可以得到結論成立。接著證明對于n≥10也成立,假設結論對于所有階數小于n的極大外平面圖都是成立的。令G為1個極大外平面圖且|V(G)|=n,則一定存在1個頂點u且d(u)=2,N(u)={v,w}。設G′=G-u,則G′為1個極大外平面圖且|V(G′)|=n-1,其中n-1≡1(mod 4)。

(1)

(3)若n=8,則H8={H?i}(i=1,2,…,12)(見圖3),根據計算,有

ξ(H?1)=17,ξ(H?2)=20,ξ(H?3)=19,ξ(H?4)=19,ξ(H?5)=20,ξ(H?6)=20,

ξ(H?7)=20,ξ(H?8)=21,ξ(H?9)=20,ξ(H?10)=24,ξ(H?11)=21,ξ(H?12)=24。

結論對于n=8成立。

接著證明對于n≥12結論也是成立的。假設結論對于階數小于n的所有極大外平面圖都是成立的。設G為極大外平面圖且|V(G)|=n,則一定存在1個頂點u且d(u)=2,N(u)={v,w}。設G′=G-u,則G′為1個極大外平面圖且|V(G′)|=n-1,其中n-1≡3(mod 4)。

(2)

則

綜上可知,可知定理2得證。