張旻劭，馬小玲

(新疆大學 數(shù)學與系統(tǒng)科學學院，新疆 烏魯木齊 830017)

0 引言

本文考慮的圖均為簡單連通圖.設(shè)圖G=(V(G),E(G)),其中V(G) 是G 的頂點集,E(G) 是G 的邊集.我們用n=|V(G)| 和m=|E(G)| 分別表示圖G 的頂點數(shù)和邊數(shù).dG(u) 表示點u 在圖G 中的度數(shù).設(shè)Δ(G) 和δ(G)分別為圖G 的最大度和最小度.對于其他未定義的術(shù)語和概念,讀者們可參閱文獻[1].

拓撲指標是分子結(jié)構(gòu)的數(shù)學描述符,被用來反映分子的大小,形狀等結(jié)構(gòu)特征,以此實現(xiàn)分子結(jié)構(gòu)信息的數(shù)值化.由于分子拓撲指標計算簡便,取值客觀且不受實驗的限制,因此應(yīng)用非常廣泛,現(xiàn)已有200 多種不同類型的拓撲指標被提出.常見的拓撲指標有Wiener指標,Randi′c指標,Zagreb指標,Hosoya指標等,可參閱文獻[2-3].2010 年,Vukicevic和Gasperov[4]引入一個基于頂點度的圖G的拓撲指標,即:逆和反度指標ISI(G),定義為其中du為圖G 中點u 的度.在2017 年,Falahati-Nezhad[5]等學者用懸掛點的個數(shù),最大度和最小度,半徑等結(jié)構(gòu)參數(shù)得到了ISI 指標的一些上下界.更多的有關(guān)ISI 指標的上下界的研究,我們可以參閱文獻[6-9].近年來,一些學者研究了圖運算,常見的圖運算有笛卡兒積運算,冠運算,對稱差運算等.關(guān)于圖運算的研究,我們可以參閱文獻[10-13].

1 準備工作

在這部分,我們首先給出一些拓撲指標和圖運算的定義,這些內(nèi)容將在我們后續(xù)的研究中起到重要的作用.1972年Gutman和Trinajstic[14]提出了第一Zageb指標和第二Zageb指標,分別定義為M1有關(guān)Zageb指標的歷史背景和性質(zhì),我們可以參閱文獻[15-16].

設(shè)圖G1=(V(G1),E(G1)),G2=(V(G2),E(G2)),其中{u1,u2,···,un1}∈V(G1),{v1,v2,···,vn2}∈V(G2),圖G1,G2的邊數(shù)分別為|E(G1)|=m1,|E(G2)|=m2.

圖連接運算,記為:G1∨G2,圖G1和G2的圖連接運算就是將G1中的每個頂點都連接到G2的每個頂點,同時保持G1和G2的原有邊.G1∨G2的頂點集為V(G1∨G2)=V(G1)∪V(G2),邊集為E(G1∨G2)=E(G1)∪E(G2)∪{uv|u ∈V(G1),v ∈V(G2)}.

笛卡兒積運算記為:G1×G2.G1×G2的頂點集為V(G1×G2)=V(G1)×V(G2),邊集為E(G1×G2)={(u1,v1)(u2,v2)|u1=u2且v1v2∈E(G2),或者v1=v2且u1u2∈E(G1)}[17].

冠運算記為:G1°G2,是由一個G1和n1個G2的拷貝得到,并且G1的第i個頂點和G2的第i 個拷貝的所有頂點相連接而得到的圖[8].

字典序積記為:G1[G2].G1[G2]的頂點集為V(G1[G2])=V(G1)×V(G2),邊集為E(G1[G2])={(u1,v1)(u2,v2)|u1u2∈E(G1),或者u1=u2且v1v2∈E(G2)}[18].

對稱差記為:G1⊕G2.G1⊕G2的頂點集為V(G1⊕G2)=V(G1)×V(G2),邊集為E(G1⊕G2)={(u1,v1)(u2,v2)|u1u2∈E(G1) 或者v1v2∈E(G2),但兩者不能同時存在}[19].顯然,

2 結(jié)論

接下來,我們將給出運算圖的逆和反度指標的上界.

定理1設(shè)Gi是有ni個點,mi條邊的簡單連通圖,其最大度是Δi,最小度是δi(i=1,2).那么

等號成立當且僅當G1和G2都是正則圖.

證明設(shè)V(G1)={u1,u2,···,un1},V(G2)={v1,v2,···,vn2}.由圖連接運算定義,如果u 是G1∨G2的一個點,那么

定理2設(shè)Gi是有ni個點,mi條邊的簡單連通圖,其最大度和最小度分別為Δi,δi其中i=1,2.那么

等號成立當且僅當G1和G2都是正則圖.

證明設(shè)V(G1)={u1,u2,···,un1},V(G2)={v1,v2,···,vn2}.根據(jù)兩個圖的笛卡兒積運算的定義,可以得到經(jīng)過圖運算后圖中每個點的度,即:

定理3設(shè)G1=(V(G1),E(G1)),G2=(V(G1),E(G2))為簡單圖,其中對于i=1,2,有|V(Gi)|=ni,|E(Gi)|=mi,其最大度和最小度分別為Δi,δi.那么

等號成立當且僅當G1和G2都是正則圖.

證明根據(jù)兩個圖的冠運算的定義,設(shè)其邊集可分為三部分,即:E(G1°G2)=E1∪E2∪E3,其中

對于點u ∈V(G1°G2),點u 的度為

因此可以得到

定理4對于i=1,2,設(shè)Gi=(V(Gi),E(Gi))為簡單圖,其中|V(Gi)|=ni,|E(Gi)|=mi,他們的最大度是Δi,最小度是δi.則有

等號成立當且僅當G1和G2都是正則圖.

證明設(shè)G1的頂點集為V的頂點集根據(jù)兩個圖字典序積的定義,可知經(jīng)過圖運算后得到的圖中每個點的度,即

等式成立當且僅當dG1(u1)=dG1(u2)=Δ1=δ1,dG2(v1)=dG2(v2)=Δ2=δ2,對于ui∈V(G1) 并且vi∈V(G2).因此,圖G1和圖G2都是正則圖.

定理5設(shè)Gi=(V(Gi),E(Gi))為簡單圖,對于i=1,2.設(shè)|V(Gi)|=ni,|E(Gi)|=mi,其最大度為Δi,最小度為δi.那么

等號成立當且僅當G1和G2都是正則圖.