李志豪， 朱 焱

（ 華東理工大學(xué)數(shù)學(xué)學(xué)院，上海 200237）

拓?fù)渲笜?biāo)是與圖的化學(xué)結(jié)構(gòu)相關(guān)聯(lián)的一種數(shù)學(xué)方法，分子圖的拓?fù)渲笜?biāo)值不僅可以定量地表達(dá)分子的結(jié)構(gòu)，也能用來分析分子的結(jié)構(gòu)與活性之間的關(guān)系，并且這些拓?fù)渲笜?biāo)值在圖的自同構(gòu)下是不變的，所以它已成功地與有機(jī)分子的物理和化學(xué)性質(zhì)相關(guān)聯(lián)，因此對于拓?fù)渲笜?biāo)的研究至關(guān)重要。但研究難點(diǎn)在于有些化合物分子比較復(fù)雜，拓?fù)渲笜?biāo)的計(jì)算量比較大。

Onagh[6]研究了關(guān)于字典序乘積圖的F-和的調(diào)和指標(biāo)。Akhter 等[7]研究了關(guān)于笛卡爾乘積圖的F-和的廣義和連通度指標(biāo)。Du等[8]研究了當(dāng)非零實(shí)數(shù)大于或等于?1時(shí)，具有n個(gè)頂點(diǎn)的單圈圖的廣義和連通度指標(biāo)的最小值和次最小值，并且確定了相對應(yīng)的極圖。Tomescua 等[9]確定了不同樹的廣義和連通度指標(biāo)的最小值。

本文把基于笛卡爾乘積下運(yùn)算圖的廣義和連通度指標(biāo)上下界推廣到基于字典序乘積下運(yùn)算圖的廣義和連通度指標(biāo)的上下界，然后計(jì)算了基于字典序乘積下運(yùn)算圖的廣義和連通度指標(biāo)的上下界，并對于每一個(gè)定理都分別給出了一個(gè)運(yùn)算圖的例子，計(jì)算了其廣義和連通度指標(biāo)，同時(shí)與定理中的上下界進(jìn)行比較，從而驗(yàn)證了定理。

1 基本概念

令G是一個(gè)有限、簡單、連通的無向圖，其點(diǎn)集和邊集分別為V=V(G) ，E=E(G) 。對于任意頂點(diǎn)v∈V，dG(v)表示v的度。Pn表示有n個(gè)頂點(diǎn)的路。對于給定的連通圖G，4種相關(guān)圖[10]定義如下：

(1) 在圖G的每條邊上嵌入一個(gè)新的頂點(diǎn)，將新頂點(diǎn)與所對應(yīng)邊的兩個(gè)端點(diǎn)連接，這樣圖G中的每條邊就變成了長為2的路，由此得到的圖記為S(G) 。

(2) 在圖G的每條邊外，都加一個(gè)與之相對應(yīng)的新的頂點(diǎn)，然后再把每個(gè)新的頂點(diǎn)與其相對應(yīng)邊的兩個(gè)端點(diǎn)連接，由此得到的圖記為R(G) 。

(3) 在圖G的每條邊上嵌入一個(gè)新頂點(diǎn)，將新頂點(diǎn)與所對應(yīng)邊的兩個(gè)端點(diǎn)連接，然后再把圖G中相鄰兩條邊所對應(yīng)的新頂點(diǎn)連接起來，由此得到的圖記為Q(G) 。

(4) 在圖G的每條邊外，都加一個(gè)與之相對應(yīng)的新的頂點(diǎn)，再把每個(gè)新的頂點(diǎn)與其相對應(yīng)邊的兩個(gè)端點(diǎn)連接，然后再把圖G中相鄰兩條邊所對應(yīng)的新的頂點(diǎn)連接起來，由此得到的圖記為T(G) 。

如果G為P6，則S(P6) ，R(P6) ，Q(P6) 和T(P6)分別如圖1所示。

圖1 F∈{S,R,Q,T} 時(shí)F(P6)的4種運(yùn)算Fig. 1Fouroperations ofF(P6)atF∈{S,R,Q,T}

兩個(gè)連通圖G0和G1的字典序乘積G0[G1] 定義為：其點(diǎn)集為V(G0)×V(G1) ，其圖中的兩個(gè)點(diǎn) (a1,b1)和 (a2,b2) 相鄰當(dāng)且僅當(dāng)a1與a2在G0中相鄰或者b1與b2在G1中相鄰且a1=a2[11]。

Sarala等[12]在兩個(gè)連通圖G0和G1的字典序乘積的基礎(chǔ)上介紹了圖的4種新運(yùn)算。

令F∈{S,R,Q,T} ，則G0和G1關(guān)于字典序乘積的F-和G0[G1]F定義為F(G0)[G1]?E?，其中E?={(a,b1)(a,b2)∈E(F(G0)[G1]):a∈V(F(G0))?V(G0)，b1b2∈E(G1)}。

若G0=G1=P3，則P3[P3]S，P3[P3]Q，P3[P3]R，P3[P3]T如圖2所示。

圖2 F∈{S,R,Q,T} 時(shí)圖P3[P3]的4種運(yùn)算Fig. 2 Four operations on graph P3[P3] at F ? {S,R,Q,T}

2 主要結(jié)果

本文確定了關(guān)于字典序乘積圖的F-和的廣義和連通度指標(biāo)的上下界。令n1,m1分別表示圖G0的頂點(diǎn)數(shù)和邊數(shù)，n2,m2分別表示G1的頂點(diǎn)數(shù)和邊數(shù)， δG0和 ?G0分別表示圖G0的最小度和最大度， δG1和 ?G1分別表示圖G1的最小度和最大度。本文首先考慮F=S。

定理1當(dāng) α 為負(fù)數(shù)，廣義和連通度指標(biāo)滿足不等式γ1(S)≤χα(G0[G1]S)≤γ2(S)，其中，

證明：

由于對于a1∈V(G0) ，有dS(G0)(a1)=dG0(a1) ，所以式（1）成立。

由等式 |E(S(G0))|=2|E(G0)|=2m1，當(dāng)a2∈V(S(G0))?V(G0) 時(shí)，dS(G0)(a2)=2 ，所以

[n2dG0(a1)+dG1(b1)+2n2]α≥2m1n22(n2?G0+?G1+2n2)α

同理可得

不等式取等號當(dāng)且僅當(dāng)圖G0和G1均為正則圖。

為了驗(yàn)證定理1的上下界，本文舉例1說明。

例1：當(dāng)G0=P4,G1=P2時(shí)，

χα(G0[G1]S)=2×6α+2×10α+8×7α+16×9α

γ1(S)=4×10α+24×9α

γ2(S)=4×6α+24×7α

滿足 γ1(S)≤χα(G0[G1]S)≤γ2(S) 。

定理2當(dāng)F=R時(shí)，對于負(fù)數(shù) α ，廣義和連通度指標(biāo)滿足不等式 γ1(R)≤χα(G0[G1]R)≤γ2(R) ，其中

不等式取等號當(dāng)且僅當(dāng)圖G0和G1均為正則圖。

證明：

由于 δG0≤dG0(a)≤?G0,δG1≤dG1(b)≤?G1，不等式取等號當(dāng)且僅當(dāng)圖G0和G1均為正則圖，因此可以得到

由于對于a1∈V(G0) ，有dR(G0)(a1)=2dG0(a1) ，所以式（2）成立。

由于dR(G0)(a1)=2dG0(a1) 、a1a2∈E(R(G0)) 和a1,a2∈V(G0) 當(dāng)且僅當(dāng)a1a2∈E(G0) ，因此

由等式 |E(R(G0))?E(G0)|=2|E(G0)|=2m1，當(dāng)a1∈V(G0) 時(shí)，dR(G0)(a1)=2dG0(a1) ；當(dāng)a2∈V(R(G0))?V(G0)時(shí)，dR(G0)(a2)=2 ，所以

不等式取等號當(dāng)且僅當(dāng)圖G0和G1均為正則圖。

為了驗(yàn)證定理2的上下界，本文舉例2說明。

例2：當(dāng)G=P4,H=P2時(shí)，

滿足 γ1(R)≤χα(G0[G1]R)≤γ2(R) 。

定理3當(dāng)F=Q時(shí)，對于負(fù)數(shù)α，廣義和連通度指標(biāo)滿足不等式γ1(Q)≤χα(G0[G1]Q)≤γ2(Q)，其中

不等式取等號當(dāng)且僅當(dāng)圖G0和G1均為正則圖。

證明：

由于 δG0≤dG0(a)≤?G0,δG1≤dG1(b)≤?G1，不等式取等號當(dāng)且僅當(dāng)圖G0和G1均為正則圖，因此可得

由于對于a1∈V(G0) ，有dQ(G0)(a1)=dG0(a1) ，所以式（3）成立。

由于a1和a2分別對應(yīng)于G0中的邊wiwj和wjwk，因此

不等式取等號當(dāng)且僅當(dāng)圖G0和G1均為正則圖。

為了驗(yàn)證定理3的上下界，本文舉例3說明。

例3： 當(dāng)G=P4,H=P2時(shí)，

定理4當(dāng)F=T時(shí)，對于負(fù)數(shù) α ，廣義和連通度指標(biāo)滿足不等式 γ1(T)≤χα(G0[G1]T)≤γ2(T) ，其中

不等式取等號當(dāng)且僅當(dāng)圖G0和G1均為正則圖。

為了驗(yàn)證定理4的上下界，本文舉例4說明。

例4： 當(dāng)G=P4,H=P2時(shí)，

χα(G0[G1]T)=2×10α+8×11α+16×14α+8×15α+8×17α+6×18α

γ1(T)=16×18α+8×16α+24×17α

γ2(T)=8×8α+24×9α+16×10α

滿足 γ1(T)≤χα(G0[G1]T)≤γ2(T) 。

3 結(jié) 論

本文先給出了基于字典序乘積的4種運(yùn)算，并得到運(yùn)算圖中頂點(diǎn)的度與未做運(yùn)算的圖的度之間的關(guān)系，再利用最大度和最小度計(jì)算了在 α＜0 的情況下基于字典序乘積的圖的4種運(yùn)算下的廣義和連通度指標(biāo)上下界，即 γ1(F)≤χα(G0[G1]F)≤γ2(F) ，其中F∈{S,R,Q,T}。如果α，>0那么γ2(F)≤χα(G0[G1]F)≤γ1(F)。因此對于其他的不同乘積，也可以把這4種運(yùn)算推廣到其他乘積上面，同樣找出乘積圖中頂點(diǎn)的度與圖G0、G1中頂點(diǎn)的度之間的數(shù)量關(guān)系，再利用最大度最小度求出廣義和連通度指標(biāo)的上下界。不過困難的是對于有些乘積，很難找出乘積圖中頂點(diǎn)的度與原圖中頂點(diǎn)的度之間的關(guān)系。