洪文豪,湯自凱

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

圖的拓?fù)渲笖?shù)是圖的不變量,能很好的體現(xiàn)圖的性質(zhì)。它不僅能夠?qū)崿F(xiàn)分子結(jié)構(gòu)信息的數(shù)值化,還能夠反映出化合物的物理化學(xué)性質(zhì)和生物活性,在化合物的定量結(jié)構(gòu)—性質(zhì)關(guān)系(QSPR)和定量結(jié)構(gòu)—活性關(guān)系(QSAR)的研究中具有重要的應(yīng)用。多個(gè)關(guān)于圖的非正則性拓?fù)渲笖?shù)被提出,如:1957年由Collatz和Sinogowitz[1]提出了最早的度量圖的非正則性的指數(shù);1997年irregularity指數(shù)被Albertson[2]提出。2005年Nikforov[3]提出了另一個(gè)非正則性拓?fù)渲笖?shù)—圖的度偏差指數(shù):,并證明了一般圖關(guān)于s(G)與鄰接譜的幾個(gè)不等式。隨后對(duì)度偏差指數(shù)的研究相繼展開:Oliveira等[4]給出了圖n,p,1PC關(guān)于s(G)的極值及其極值圖并提出一般圖在CS(n,k)處取得極值的猜想;Ghalavand等[5]解決了文獻(xiàn)[4]的猜想并計(jì)算了一些化學(xué)圖關(guān)于s(G)的值;劉樂樂等[6]研究了k-均勻超圖關(guān)于s(G)的值;關(guān)于度偏差指數(shù)的更多研究可見文獻(xiàn)[7-9]。而仙人掌圖是經(jīng)常被研究的對(duì)象,仙人掌圖關(guān)于irregularity-指數(shù)、ABC-指數(shù)、Sombor-指數(shù)、Mostar-指數(shù)、Randic-指數(shù)的極值問題等已經(jīng)被廣泛研究[10-14]。在本文中,僅考慮簡單、無向、連通和有限的圖。利用分支變換、縮圈變換等圖形變換給出了仙人掌圖關(guān)于度偏差指數(shù)的極值以及極值圖。

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

設(shè)圖G=(V,E),其中V,E分別表示圖的頂點(diǎn)集與邊集,令。

dG(vi)表示圖G中頂點(diǎn)vi的度(不混淆的情況下可簡寫為d(vi) ); 序列(d1,d2,…,di,…,dn)表示圖G的度序列,其中di=d(vi)且d1≤d2≤…≤dn,nj(1 ≤j≤n-1)表示圖G中頂點(diǎn)度為j的個(gè)數(shù);N(v)表示頂點(diǎn)v的所有鄰點(diǎn)的集合。設(shè)C表示一個(gè)圈,Ci是第i(1 ≤i≤k)個(gè)圈。設(shè)P=u0u1...ul(l≥ 1) 是一條路,若滿足d(u0)≥ 3,d(ul)= 1 ,d(ui) = 2(1 ≤i≤l-1)則稱P為懸掛路;當(dāng)l=1,d(ul)= 1 時(shí),則稱ul為懸掛點(diǎn),ulu0為懸掛邊;若d(u0)≥ 3,d(ul)≥ 3 ,d(ui)=2(1≤i≤l-1),則P稱為圖G的內(nèi)部路,Pn表示n個(gè)頂點(diǎn)的路。u～v表示頂點(diǎn)u和v相鄰。若任意2個(gè)圈至多有1個(gè)共享頂點(diǎn)的連通圖,則稱為仙人掌圖。設(shè)?n,k表示有n個(gè)頂點(diǎn),k個(gè)圈的仙人掌圖,Gn,k∈?n,k表示有n個(gè)頂點(diǎn),k個(gè)不相交的三角形和n-2k-1條懸掛邊共享1個(gè)頂點(diǎn)的仙人掌圖。記Sn為星圖,則Sn+e表示在星圖Sn的2個(gè)懸掛點(diǎn)之間加1條邊e。Sn+e,Gn,k如圖1所示。沒有提到的定義或術(shù)語參見文獻(xiàn)[15]。

若圖G∈?n,k,顯然圖G有n+k-1條邊,則。若1個(gè)圈中有且只有1個(gè)頂點(diǎn)度大于2,則稱為終端圈。為了證明主要結(jié)論將使用以下3個(gè)簡單引理和2個(gè)圖形變換。

引理1設(shè)圖G∈?n,k,k≥2則。

證明首先由n≥ 2k+1可得2k- 2 ≤n- 3 ,所以。故

命題得證。

由引理1知,s(G)只與n1,n2有關(guān)。

1.1 仙人掌圖的分支變換

引理2(分支變換) 設(shè)圖G是含k(k≥ 2 )個(gè)圈的仙人掌圖,其中有p(2 ≤p≤k)個(gè)圈(不一定是終端圈)共點(diǎn),若存在va∈V(G)是不與共享頂點(diǎn)相同的點(diǎn)。圖G＇由圖G將p個(gè)圈中的某個(gè)圈移到頂點(diǎn)va所得。則s(G)-s(G＇)≥ 0。

證明圖G到圖G＇的分支變換如圖2所示。在圖G中分d(va)=1,d(va)=2和d(va)≥ 3 3種情況考慮。當(dāng)d(va)=1時(shí),則圖G＇中dG＇(va)＞2,即減少1個(gè)一度頂點(diǎn),由引理1得s(G)-s(G＇)=2(1+(2k-2)/n)＞ 0; 當(dāng)d(va)=2時(shí),則圖G＇中dG＇(va)＞2,即減少1個(gè)二度頂點(diǎn),由引理1得s(G)-s(G＇)=2(2k-2)/n＞0;當(dāng)d(va)≥ 3時(shí),則圖G＇中n1,n2無變化,由引理1得s(G)-s(G＇)=0。綜上所述,s(G)-s(G＇)≥ 0。命題得證。

1.2 仙人掌圖的縮圈變換

引理3(縮圈變換) 設(shè)圖G是含k(k≥ 2)個(gè)圈的仙人掌圖,若圖G中存在一個(gè)圍長大于3的圈C(不一定是終端圈)與一條端點(diǎn)度為3的內(nèi)部路P共點(diǎn),設(shè)v1是其共享頂點(diǎn)且v1,v2,v3∈V(C),v1～v2,v1～v3。圖G＇由圖G去掉邊v1v3和增加邊v2v3所得。則s(G) -s(G') ≤ 0 。

證明圖G到圖G＇的縮圈變換如圖3所示。在圖G中分d(v2)＞2和d(v2)=2 2種情況考慮。當(dāng)d(v2)＞ 2時(shí),則圖G＇中dG＇(v1)=2,即增加了1個(gè)二度頂點(diǎn),由引理1可得s(G)-s(G＇)=-2（2k-2)/n＜ 0; 當(dāng)d(v2)=2時(shí),顯然圖G＇中n1,n2無變化,由引理1可得s(G)-s(G＇)=0。綜上所述,s(G)-s(G＇)≤0。命題得證。

2 仙人掌圖的極值

下面先給出樹關(guān)于度偏差指數(shù)的極值及相關(guān)極值圖。

定理1若G∈?n,0,n≥2，即圖G是樹,則,其中當(dāng)且僅當(dāng)G?Pn時(shí),左邊不等式取等;當(dāng)且僅當(dāng)G?Sn時(shí),右邊不等式取等。

證明由,有。顯然s(G)隨著n1增大而增大。又在樹中有 2 ≤n≤1n- 1 ,所以n1=2當(dāng)時(shí),即;當(dāng)n=n- 1時(shí),即1。定理得證。

下面將給出單圈圖關(guān)于度偏差指數(shù)的極值及相關(guān)極值圖。

定理2若G∈?n,1,n≥3,即圖G是單圈圖,則0 ≤s(G) ≤ 2n-6,其中當(dāng)且僅當(dāng)G?C時(shí),左邊不等式取等;當(dāng)且僅當(dāng)G?Sn+e時(shí),右邊不等式取等。

證明由,有。顯然s(G)只與n1有關(guān)。又因?yàn)樵趩稳DG中有 0 ≤n≤n-3,所1以當(dāng)n1=0時(shí),即G?C,s(G)min=0;當(dāng)n1=n- 3 時(shí),即G?Sn+e,s(G)max=2n-6。定理得證。

因?yàn)楫?dāng)k≥ 2時(shí)，頂點(diǎn)個(gè)數(shù)n≤ 4的仙人掌圖不存在。下面將給出k≥ 2,n≥ 5的仙人掌圖關(guān)于度偏差指數(shù)的極大值,并刻畫唯一達(dá)到極大值的仙人掌圖。

定理3若G∈?n,k,(k≥2,n≥5),則s(G) ≤ 2n- 6 - (4k-4)/n,當(dāng)且僅當(dāng)G?Gn,k時(shí)等號(hào)成立。

證明首先由引理1有。其次根據(jù)仙人掌圖的定義有n1+n2≤n- 1 ,n1≤n-2k-1。因此,只有當(dāng)n1+n2=n- 1時(shí),才能實(shí)現(xiàn)s(G)取最大值。又由引理1可知在s(G)的表達(dá)式中n1的系數(shù)比n2的系數(shù)大,所以當(dāng)n1=n-2k-1,n2=2k時(shí),即G?Gn,k,s(G)max=2n-6-(4k-4)/n。定理得證。

下面將給出k≥ 2,n≥ 5的仙人掌圖關(guān)于度偏差指數(shù)的極小值,并刻畫能達(dá)到極小值的仙人掌圖類。

定理4設(shè)G∈?n,k,(k≥2,n≥5)。

(1)當(dāng)n/ 3 ＜k≤ (n - 1 )/2時(shí),有s(G) ≥ 2(k+ 2 )(2k-2)/n,當(dāng)且僅當(dāng)圖G的度序列滿足(2,...2,3,...,3,4,...,4)時(shí),等號(hào)成立,其中n2=k+ 2 ,n3= 2(n- 2k- 1 ),n4=3k-n;

如圖4所示給出了3個(gè)特殊的達(dá)到極小值的仙人掌圖;如圖5所示給出了3個(gè)特殊的達(dá)到極小值的仙人掌圖。

證明下面逐步刻畫達(dá)到極小值的仙人掌圖的特點(diǎn),從而求得極小值。

斷言1若圖G是關(guān)于度偏差指數(shù)的極小值圖,則圖G中不存在懸掛路(點(diǎn))。

證明(斷言1) 假設(shè)圖G中存在懸掛路。設(shè)懸掛路Pi=v1v2. ..viv0,且d(v1)=1,d(v0)≥ 3 。在圖G中存在va∈N(v0)且d(va)≥ 2 ,,設(shè)G＇由圖G去掉邊v0va和增加邊v1va所得,即G' =G-v0va+v1va,如圖6所示。下面分d(v0)=3和d(v0) ＞ 3 2種情況考慮。當(dāng)d(v0)=3時(shí),圖G＇中dG'(v0) =dG'(v1) = 2 ,即增加了2個(gè)二度頂點(diǎn),減少了1個(gè)一度頂點(diǎn),由引理1得;當(dāng)d(v0) ＞ 3 時(shí),圖,即增加了1個(gè)二度頂點(diǎn),減少了1個(gè)一度頂點(diǎn),由引理1得。故與假設(shè)矛盾。由此可得極小值圖G中不存在懸掛路。同理,也不存在懸掛點(diǎn)。

由斷言1知極小值圖G中無一度頂點(diǎn),故s(G)只與n2有關(guān)。

斷言2若圖G是關(guān)于度偏差指數(shù)的極小值圖,則圖G中不存在p(p≥ 3 )個(gè)圈(這些圈不一定是終端圈)共享1個(gè)頂點(diǎn)。

證明(斷言2) 假設(shè)存在p(p≥ 3 )個(gè)圈(這些圈不一定是終端圈)共享1個(gè)頂點(diǎn)。由斷言1可得圖G中所有頂點(diǎn)滿足d(v)≥2,再根據(jù)引理2的分支變換,把p個(gè)圈中的某個(gè)圈移到1個(gè)二度頂點(diǎn)處,則此時(shí)圖G＇中減少1個(gè)二度頂點(diǎn),所以s(G)-s(G＇)=2(2k-2)/n＞0。故與假設(shè)矛盾。由此可得極小值圖G中最多只有2個(gè)圈共點(diǎn)。

特別的,當(dāng)k=(n-1)/2時(shí),可得到唯一的極小值圖G且度序列為(2,…,2,4,…,4),其中n2=k+2,n4=k-1。下面考慮k＜(n-1)/2的情況。

斷言3若圖G是關(guān)于度偏差指數(shù)的極小值圖且k＜(n-1)/2,則極小值圖G中不存在端點(diǎn)度大于3的內(nèi)部路。

證明(斷言3) 假設(shè)存在端點(diǎn)v1,v2的度大于3的內(nèi)部路P。不妨設(shè)d(v1)＞3,由仙人掌圖的定義可知去掉v1之后圖G至少有3個(gè)分支G1,G2,G3。設(shè)v1,v2,va∈V(P),且滿足v1～va。又因極小值圖G中必存在1個(gè)二度頂點(diǎn)v3,不失一般性地設(shè)v3∈V(G3)。設(shè)G＇由圖G去掉邊v1va和增加邊v3va所得,即G＇=G-v1va+v3va,如圖7 所示。顯然圖G＇中dG＇(v3)＞2,即減少1個(gè)二度頂點(diǎn),由引理1得s(G)-s(G＇)=2(2k-2)/n＞0。故與假設(shè)矛盾。由此可得極小值圖G中內(nèi)部路的端點(diǎn)度等于3。

當(dāng)k＜(n-1)/2時(shí),由上知極小值圖G的度序列只能是(2,…,2,3,…,3,4,…,4),此時(shí)度為2,3,4的頂點(diǎn)個(gè)數(shù)不知,下面我們繼續(xù)尋找極小值圖G對(duì)應(yīng)的度為2,3,4的頂點(diǎn)個(gè)數(shù)。

斷言4若圖G是關(guān)于度偏差指數(shù)的極小值圖且圈的個(gè)數(shù)k＜(n-1)/2,則極小值圖G中不存在圍長大于3的圈與其它圈共點(diǎn)。

證明(斷言4) 假設(shè)圖G中存在一個(gè)圍長大于3的圈C1與另一個(gè)圈C2共點(diǎn)。設(shè)v1是其共享頂點(diǎn),v1,v2,v3∈V(C1) 且v1～v2,v1～v3。設(shè)圖G＇由圖G去掉邊v1v3和增加邊v2v3，即G＇=G-v1v3+v2v3,如圖8所示。

下面分d(v2)＞2和d(v2)=2 2種情況考慮。當(dāng)d(v2)＞2時(shí),則圖G中n1,n2無變化且有dG＇(v2)＞3,但由斷言3可知極小值圖G中不存在端點(diǎn)度大于3的內(nèi)部路,故與假設(shè)矛盾;當(dāng)d(v2)=2時(shí),顯然圖G＇中dG＇(v2)＞2,即減少1個(gè)二度頂點(diǎn),由引理1得s(G)-s(G＇)=2(2k-2)/n＞0。故與假設(shè)矛盾。由此可得極小值圖中圍長大于3的圈必與內(nèi)部路相連或若2個(gè)圈共點(diǎn),則圈必是三角形。

斷言5若圖G是關(guān)于度偏差指數(shù)的極小值圖且n/3＜k＜(n-1)/2,則極小值圖G中不存在長度大于1的內(nèi)部路和圍長大于3的圈。

證明(斷言5) 假設(shè)存在長度大于1的內(nèi)部路和圍長大于3的圈。因?yàn)閳DG中可能存在圍長大于3的圈,由斷言3和斷言4可知引理3中的v2滿足d(v2)=2,則可通過縮圈把圖G中所有的圍長大于3的圈變成三角形且不改變s(G)的值,此時(shí)圖G中只存在長度大于1的內(nèi)部路。設(shè)一條長大于1的內(nèi)部路為P,則肯定存在2個(gè)共點(diǎn)的三角形和內(nèi)部路P在一條鏈L上。(1)若P與2個(gè)共點(diǎn)的三角形相鄰,設(shè)v2是其共享頂點(diǎn),v1,v2∈V(P)且v1～v3,v2～v3,v2～v4,設(shè)圖L＇由圖L去掉邊v3v4和增加邊v3v1,即L＇=L-v3v4+v3v1如圖9所示。顯然L＇中dL＇(v1)＞ 2,即減少 1 個(gè)二度頂點(diǎn),由引理1得s(G)-s(G＇)=2(2k-2)/n＞0,故與假設(shè)矛盾。(2)若P與2個(gè)共點(diǎn)的三角形不相鄰,則在鏈L上找到離P最近的2個(gè)共點(diǎn)的三角形,設(shè)v1,v2∈V(P)且v2是離2個(gè)共點(diǎn)的三角形最近的P的1個(gè)端點(diǎn)和v1～v2,va,vb,vc是離v2最近的2個(gè)共點(diǎn)的三角形上的3個(gè)點(diǎn)。去掉邊vavb、vavc,把va往P處滑動(dòng)再添加邊v1va、v2va,然后再把va所經(jīng)過的所有三角形往右邊滑動(dòng)一格,此時(shí)得到L＇,如圖10所示。顯然L＇中dL＇(v1)＞2,即減少1個(gè)二度頂點(diǎn),由引理1得s(G)-s(G＇)=2(2k-2)/n＞ 0。故與假設(shè)矛盾。所以通過圖9、10的變換可以把圖G中所有長度大于1的內(nèi)部路變成全部長度為1的內(nèi)部路,使得s(G)的值變小,此時(shí)可得到極小值圖G的度序列是(2,…,2,3,…,3,4,…,4),其中n2=k+2,n3=2(n-2k-1),n4=3k-n。

斷言6若圖G是關(guān)于度偏差指數(shù)的極小值圖且,則極小值圖G中不存在2個(gè)共點(diǎn)的三角形。

證明(斷言6) 假設(shè)存在2個(gè)共點(diǎn)的三角形。因?yàn)閳DG中圈比較少,則可通過斷言5中的圖9、10的變換把所有的共點(diǎn)的三角形拆分掉。故與假設(shè)矛盾。此時(shí)圖G再無四度頂點(diǎn),則可得到極小值圖G的度序列是(2,…,2,3,…,3),其中n2=n-2k+2,n3=2k-2。