樹(shù)的指數(shù)型反遺忘指數(shù)的極值問(wèn)題

曾明瑤 鄧漢元?

(1. 懷化學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,懷化,418000；2. 湖南師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,長(zhǎng)沙,410081)

1 引言

拓?fù)渲笖?shù)起源于1947 年,Wiener 提出在化學(xué)中用拓?fù)渲笖?shù)研究分子結(jié)構(gòu)圖的相關(guān)性質(zhì). 此后,科研工作者們提出了一系列用來(lái)描述分子結(jié)構(gòu)圖的各種數(shù)學(xué)、化學(xué)性質(zhì)的拓?fù)渲笖?shù). 在數(shù)學(xué)、化學(xué)文獻(xiàn)中,有大量的分子結(jié)構(gòu)描述符(拓?fù)渲笖?shù)),被用于研究分子結(jié)構(gòu)之間的相關(guān)性. 一個(gè)特殊的類(lèi)別是基于頂點(diǎn)度的拓?fù)渲笖?shù)(簡(jiǎn)稱(chēng)VDB 拓?fù)渲笖?shù)),它在圖中的研究備受學(xué)者青睞.

1972 年,一些化學(xué)家在研究π-電子能量結(jié)構(gòu)的依存性時(shí),發(fā)現(xiàn)能量依賴(lài)于分子結(jié)構(gòu)圖頂點(diǎn)度的平方和(也就是后來(lái)定義的第一類(lèi)Zagreb 指數(shù)),同時(shí)發(fā)現(xiàn)頂點(diǎn)度的立方和對(duì)能量也有影響[1],但這類(lèi)拓?fù)渲笖?shù)卻未被進(jìn)一步研究,而是被遺忘,因此稱(chēng)為遺忘指數(shù).

在數(shù)學(xué)、化學(xué)文獻(xiàn)中, 目前已有一些關(guān)于遺忘指數(shù)的研究, 如Furtula, Gutman[2]以第一類(lèi)Zagreb 指數(shù)和第二類(lèi)Zagreb 指數(shù)為橋梁,給出了關(guān)于圖的遺忘指數(shù)的界；Li 和Zhao 在[3]中討論樹(shù)的遺忘指數(shù),得到了其極值并刻畫(huà)了對(duì)應(yīng)的極樹(shù)；Basavanagoud 和Patil[4]給出了圖與其補(bǔ)圖的遺忘指數(shù)之間的關(guān)系；Elumalal[5]等給出了給定頂點(diǎn)數(shù)、邊數(shù)、最大和最小頂點(diǎn)度的樹(shù)的遺忘指數(shù)的各種下界. 關(guān)于遺忘指數(shù)的更多研究?jī)?nèi)容可參考[6-9].

Rada 在[10]中給出了普通的VDB 拓?fù)渲笖?shù)的定義: 令Gn表示有n個(gè)非孤立頂點(diǎn)的圖集,考慮集合

φi,j選取不同形式的函數(shù)時(shí),對(duì)應(yīng)著不同的VDB 拓?fù)渲笖?shù). 有關(guān)VDB 拓?fù)渲笖?shù)的細(xì)節(jié)可參考[11-14].

為了更好地研究拓?fù)渲笖?shù)的區(qū)分性質(zhì),Rada 在[14]中介紹了指數(shù)型VDB 拓?fù)渲笖?shù). 給定一類(lèi)VDB 拓?fù)渲笖?shù)φ,指數(shù)型VDB 拓?fù)渲笖?shù)eφ定義為

G的指數(shù)型反遺忘指數(shù)定義為

遺忘指數(shù)的廣泛研究與應(yīng)用以及一系列的研究結(jié)果表明,遺忘指數(shù)與反遺忘指數(shù)在數(shù)學(xué)領(lǐng)域有重要意義. 但是關(guān)于反遺忘指數(shù)的研究結(jié)果比較少,且還沒(méi)有文獻(xiàn)對(duì)指數(shù)型反遺忘指數(shù)進(jìn)行研究. 為了更好地研究拓?fù)渲笖?shù)的判別、區(qū)分性質(zhì),指數(shù)型反遺忘指數(shù)的研究是很有必要的.

2 樹(shù)的指數(shù)型遺忘指數(shù)的極小值

在這一節(jié)中,我們考慮指數(shù)型反遺忘指數(shù)的極小值,并刻畫(huà)對(duì)應(yīng)的極圖特征. 用Tn表示所有n階樹(shù)的集合.

證明 若T中懸掛路長(zhǎng)均為1, 則存在如圖1 所示的分支點(diǎn)v ∈V(T), 滿(mǎn)足NT(v){u}={v1,v2,··· ,vy-1},其中uv ∈E(T),dT(u) =x ≥3,dT(vi)= 1(1≤i ≤y-1). 設(shè)dT(v)=y ≥2.令T′=T-{vv1,vv2,··· ,vvy-1}+{vv1,v1v2,··· ,vy-2vy-1},此時(shí)T′中有一條長(zhǎng)為y的懸掛路Py=uvv1···vy-1,且在T′中dT′(v) =dT′(v1) =dT′(v2) =···=dT′(vy-2) = 2,dT′(vy-1) = 1,則

圖1 引理1 中樹(shù)T 和樹(shù)T′

定義1([15]) 設(shè)T ∈Tn. 稱(chēng)T為毛毛蟲(chóng)樹(shù),若Pk=v1v2···vk為T(mén)中含有k個(gè)頂點(diǎn)的路,且在頂點(diǎn)v1上附著a1個(gè)懸掛點(diǎn), 在頂點(diǎn)v2上附著a2個(gè)懸掛點(diǎn),···, 在頂點(diǎn)vk上附著ak個(gè)懸掛點(diǎn),其中ai ≥0(i= 1,··· ,k). 我們稱(chēng)Pk=v1v2···vk為毛毛蟲(chóng)樹(shù)T的主路,并把這樣的樹(shù)記為cp(k;a1,a2,··· ,ak),如圖2.

圖2 毛毛蟲(chóng)樹(shù)cp(k;a1,a2,··· ,ak)

圖3 引理2 中樹(shù)T 和樹(shù)T′

接下來(lái),我們令Pk=v1v2···vk為毛毛蟲(chóng)樹(shù)cp(k;a1,a2,··· ,ak)的主路,且ak-1=ak= 0,否則由引理1 中變換,可以找到更小樹(shù)滿(mǎn)足條件.

T為毛毛蟲(chóng)樹(shù), 必然存在這樣的分支頂點(diǎn)vi, 使距離dT(vi,vk) 最短, 且ai/= 0. 不妨設(shè)dT(vi-1) =x ≥2,dT(vi+1) = 2,dT(vi) =y ≥3,vi的鄰域NT(vi) ={vi-1,vi+1,w1,··· ,wy-2},則dT(w1) =dT(w2) =···=dT(wy-2) = 1. 令T′=T-{viw1,viw2··· ,viwy-2}+{vkw1,vkw2··· ,vkwy-2}(如圖4),則

圖4 引理3 中樹(shù)T 和樹(shù)T′

3 樹(shù)的指數(shù)型遺忘指數(shù)的極大值

定義2([16,17]) 若給定樹(shù)T的度序列,則根據(jù)以下算法(1)-(4)構(gòu)造而成的樹(shù)稱(chēng)為貪婪樹(shù).

(1)標(biāo)記T中最大度頂點(diǎn)為v0,1(稱(chēng)v0,1為根)；

(2) 標(biāo)記頂點(diǎn)v0,1的鄰點(diǎn)為v1,1,v1,2,···, 且它們的頂點(diǎn)度不大于dT(v0,1), 同時(shí)滿(mǎn)足dT(v1,1)≥dT(v1,2)≥···；

(3)標(biāo)記除v0,1外,頂點(diǎn)v1,1的其余鄰點(diǎn)為v2,1,v2,2,···,且它們的頂點(diǎn)度不大于dT(v1,j)(j ≥1),同時(shí)滿(mǎn)足dT(v2,1)≥dT(v2,2)≥···；再用同樣方法標(biāo)記v1,2,v1,3,···；

(4)對(duì)于新標(biāo)記的頂點(diǎn)重復(fù)(3)的做法,直至所有頂點(diǎn)標(biāo)記完.

用h(v) 表示貪婪樹(shù)中根到頂點(diǎn)v的距離； 稱(chēng)頂點(diǎn)vi,j(i,j ≥1) 為頂點(diǎn)vi-1,j的父親, 頂點(diǎn)vi-1,j(i,j ≥1)為頂點(diǎn)vi,j的兒子.

證明 設(shè)v0為T(mén)中最大度頂點(diǎn),dT(v0) =d0= Δ,dT(vi) =di(1≤i

下面, 我們給出內(nèi)部路與懸掛路的定義. 對(duì)于圖G中一條長(zhǎng)為k的路u0u1···uk-1uk, 若dG(u0)≥3 且對(duì)于1≤i ≤k-1,有dG(ui) = 2,則當(dāng)dG(uk)≥3 時(shí),稱(chēng)它為圖G的內(nèi)部路；當(dāng)dG(uk)=1 時(shí),稱(chēng)它為圖G的懸掛路.

證明(1)首先證明T中至多只有一條長(zhǎng)度為2 的懸掛路,若T中存在兩條長(zhǎng)度為2 的懸掛路P1=uu1u2,P2=vv1v2,不妨設(shè)dT(u)=x ≤y=dT(v),2≤x ≤y. 令T′=T-u1u2+v1u2,則有

圖5 引理7 的證明中，(1)的樹(shù)T 和樹(shù)T′

(2) 若u為T(mén)中最大度頂點(diǎn)且與懸掛點(diǎn)v相鄰, 下證這條長(zhǎng)為2 的懸掛路附在頂點(diǎn)u上. 如圖6,u為T(mén)中最大度頂點(diǎn)且與懸掛點(diǎn)v相鄰,ww1w2為T(mén)中長(zhǎng)為2 的懸掛路. 設(shè)dT(u)=x ≥y=dT(w),令T′=T-w1w2+vw2,則有

圖6 引理7 的證明中，(2)的樹(shù)T 和樹(shù)T′

本文考慮了當(dāng)φij=iα+jα(α ≥1)時(shí),指數(shù)型VDB 拓?fù)渲笖?shù)∑(i,j∈K)mi,j(G)eφij取得極值時(shí),對(duì)應(yīng)的極樹(shù)的結(jié)構(gòu),并研究了當(dāng)α=-2 時(shí),對(duì)應(yīng)的反遺忘指數(shù)取得極值時(shí),對(duì)應(yīng)極樹(shù)的結(jié)構(gòu)性質(zhì).

至于α< 1 時(shí),指數(shù)型VDB 拓?fù)渲笖?shù)∑(i,j∈K)mi,j(G)eiα+jα取得極值的情況,還不能通過(guò)本文的圖變換和計(jì)算得到極值結(jié)果,這將是我們未來(lái)進(jìn)一步要研究的問(wèn)題.