關(guān)于極大外平面圖的離心率總和指數(shù)

宋玲,劉合超,湯自凱

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

拓?fù)渲笖?shù)是對分子結(jié)構(gòu)進(jìn)行數(shù)值建模的一種方法,它是通過對特征分子圖的矩陣進(jìn)行一些數(shù)字運(yùn)算而獲得的,特征圖譜是圖的不變量,該圖直接在分子結(jié)構(gòu)中生成并反映出該化合物的結(jié)構(gòu)特征。

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

HOSOYA[3]提出一種表征飽和烴異構(gòu)體性質(zhì)的指數(shù)，并且研究了它與維納指數(shù)的關(guān)系。SKOROBOGATOV和DOBRYNIN[4]定義了n個頂點(diǎn)的圖的平均離心率為

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

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

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

1 預(yù)備結(jié)論

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

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

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

圖1 頂點(diǎn)數(shù)為6時的所有的非同構(gòu)極大外平面圖Fig.1 All non-isomorphic 6-vertex maximal outerplanar graphs

圖2 頂點(diǎn)數(shù)為7時的所有的非同構(gòu)極大外平面圖Fig.2 All non-isomorphic 7-vertex maximal outerplanar graphs

圖3 頂點(diǎn)數(shù)為8時的所有的非同構(gòu)極大外平面圖Fig.3 All non-isomorphic 8-vertex maximal outerplanar graphs

圖4 圖

在文獻(xiàn)[19]中,HOU等給出了極大外平面圖的一些性質(zhì)。

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

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

圖5 圖

根據(jù)極大外平面圖的定義,可以得到下述事實(shí)。

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

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

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

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

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

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

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

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

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

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

這個結(jié)論對于n=6時成立。

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

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

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

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

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

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個頂點(diǎn)的三角形的數(shù)目?？梢钥吹疆?dāng)a≥2時,xi-1,2=xi1,i∈{2,3,4,…,a}是可能成立的。每一個三角形△i都對應(yīng)著1個外邊界為xi1xi2∪Qi的1個極大外平面圖Gi,其中Qi是外邊界上端點(diǎn)為xi1和xi2的1條路。G-{u,w}即Gi=G[V(Qi)],其中1≤i≤a。類似地,在G中有b個以w(而不是v)作為其中1個頂點(diǎn)的三角形,可以看出b≥0。用△yj1wyj2(簡寫為△′j)表示圖G中邊yj1yj2為弦的三角形?？梢钥闯霎?dāng)b≥2時,yj-1,2=yj1,j∈{2,3,4,…,b}是可能的。每一個三角形△′j都對應(yīng)著1個外邊界為yj1yj2∪Q′j的極大外平面圖G′j,其中Q′j為外邊界上端點(diǎn)為yj1和yj2的1條路。即G′j=G[V(Q′j)]。當(dāng)a=b=0時,對于任意1個頂點(diǎn)x∈V(G){v,w},vx∈E(G)和wx∈E(G)中至少有1個是成立的。用ki=|V(Qi)|-2≥1表示Qi(1≤i≤a)中既不與v相鄰也不與w相鄰的頂點(diǎn)數(shù)目,其中a≥1。類似地,當(dāng)b≥1時,用lj=|V(Q′j)|-2≥1表示Q′j(1≤j≤b)中既不與v相鄰也不與w相鄰的頂點(diǎn)數(shù)目。設(shè)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 Ⅰ

變換Ⅰ假設(shè)在極大外平面圖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個階數(shù)為n的極大外平面圖。若在G中d(v)+d(w)=k，則dG′(v)+dG′(w)=k-1。接著證明當(dāng)k≥9時,f(k-1)≥f(k)。下面分別比較G和G′中u和其他頂點(diǎn)的距離。

設(shè)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中存在點(diǎn)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|。

根據(jù)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|。

根據(jù)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|。

根據(jù)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|。

根據(jù)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)}

現(xiàn)在比較Gn-1和Gn中點(diǎn)u和其他點(diǎn)的距離。

若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|。

根據(jù)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|。

根據(jù)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為頂點(diǎn)數(shù)n≥6的1個極大外平面圖,則

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

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

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

所以，當(dāng)n=7時結(jié)論成立。

令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)。因此可得

綜上,當(dāng)n=2k+1時,有

(2)若n=6,則H6={H′1,H′2,H′3}(見圖1),根據(jù)直接的計算,可以得到結(jié)論成立。接著證明對于n≥10也成立,假設(shè)結(jié)論對于所有階數(shù)小于n的極大外平面圖都是成立的。令G為1個極大外平面圖且|V(G)|=n,則一定存在1個頂點(diǎn)u且d(u)=2,N(u)={v,w}。設(shè)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),根據(jù)計算,有

ξ(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。

結(jié)論對于n=8成立。

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

(2)

則

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