兩類圖運(yùn)算的Zagreb 離心率指標(biāo)

阿斯牙·米吉提

（喀什大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，新疆 喀什 844000）

0 引言

設(shè)圖G=(V,E)是一個簡單連通的無向圖,其中V(G)和E(G)分別表示圖的頂點(diǎn)集和邊集.對任意點(diǎn)u∈G，用degG(u)來表示點(diǎn)u的度數(shù)，且定義為從點(diǎn)u出發(fā)的邊的總數(shù)目.設(shè)u0,u1,u2,…,uk∈V(G),e0,e1,e2,…,ek∈E(G)，其中ei是關(guān)聯(lián)于結(jié)點(diǎn)ui-1和ui的邊，則稱u0e1u1e2u2e3…ekuk為連接u0到uk的路，路中邊的數(shù)目稱為路的長度.設(shè)任意兩點(diǎn)u,v∈V(G),則u,v之間的距離定義為u,v之間最短路的長度，記為dG(u,v).而點(diǎn)u到v之間的最大距離稱為點(diǎn)u的離心率，記為e(u)，即圖G的離心率的總數(shù)ζ(G)定義為圖G中所有頂點(diǎn)的離心率的總數(shù)，即ζ(G)=

圖不變量是一個從圖的集合到實(shí)數(shù)的函數(shù).在化學(xué)圖論中，圖不變量通常被稱為拓?fù)渲笜?biāo).在拓?fù)渲笜?biāo)中，文獻(xiàn)[1]中引入的Zagreb 指標(biāo)是最著名的，其中Gutman 和Trinajsti?研究了總π-電子能量對分子結(jié)構(gòu)的依賴性，并在文獻(xiàn)[2]中作了進(jìn)一步研究.第一類Zagreb 指標(biāo)和第二類Zagreb指標(biāo)分別被定義為

這兩個經(jīng)典的拓?fù)渲笜?biāo)反映了分子骨架的分支程[3].關(guān)于Zagreb 指標(biāo)的各種結(jié)果見文獻(xiàn)[4-9].與第一類和第二類Zagreb 指標(biāo)類似,Vuki?evic 和Hosseinazdeh[10]引入了Zagreb離心率指標(biāo)，并定義

為圖G的第一類Zagreb離心率指標(biāo)，記為E1(G)；

定義

為圖G的第二類Zagreb離心率指標(biāo)，記為E2(G)；

定義

為圖G的第三類Zagreb離心率指標(biāo)，記為E3(G).

最近，又有一種新的圖的點(diǎn)的離心率指標(biāo)被引入，其中有拓?fù)潆x心連通指標(biāo)、離心距離和n類離心Zagreb 指標(biāo)等.進(jìn)一步，有Xu[11]等人引入了衡量圖的非自中心數(shù)，并定義

為圖G的非自中心數(shù)，記為N(G).

關(guān)于這一指標(biāo)仍有許多問題有待研究.在本文中,我們主要討論通過圖的復(fù)合運(yùn)算與笛卡爾積運(yùn)算得到的兩類圖的以上指標(biāo)，并得到了這些圖運(yùn)算的第一、第二類、第三類Zagreb 離心率指標(biāo)以及非自中心數(shù)(NSC 數(shù))的精確表達(dá)式.

1 定義及引理

定義1.1設(shè)圖G1和G2是任意兩個無向的簡單連通圖,則G1和G2的笛卡爾積圖為G=G1×G2,其中圖G滿足：V(G)=V(G1)×V(G2)；圖G中的兩個頂點(diǎn)(u1,v1)和(u2,v2)相鄰當(dāng)且僅當(dāng)u1=u2,v1v2∈E(G2) 或者v1=v2,u1u2∈E(G1).

定義1.2設(shè)G1和G2是任意兩個無向的簡單連通圖,則圖G1和G2的復(fù)合圖G=G1[G2]是頂點(diǎn)集為V(G1)×V(G2)、并具有不相交的頂點(diǎn)集V1和V2與邊集E1和E2的圖,且圖中任意兩個頂點(diǎn)(u1,v1)和(u2,v2)相鄰當(dāng)且僅當(dāng)u1和u2相鄰或者u1=u2,且v1和v2相鄰.

引理1.1[12]設(shè)G和H是圖,則有

（1）|V(G×H) |=|V(G)||V(H) |，|E(G×H) |=|E(G)||V(H) |+|V(G)||E(H) |；

（2）G×H是連通的當(dāng)且僅當(dāng)G與H都是連通的；

（3）如果(a,c)和(b,d)都是G×H的頂點(diǎn),則有

引理1.2[13]若復(fù)合圖G[?H]是連通當(dāng)且僅當(dāng)圖G和H是連通的,則有

2 主要結(jié)果及證明

2.1 復(fù)合圖的Zagreb 離心率指標(biāo)及非自中心數(shù)

引理2.1設(shè)Pm和Pn分別為有m個頂點(diǎn)和有n個頂點(diǎn)的路,則對復(fù)合圖Pm[Pn]，有

證明由離心率的定義可知又由引理1.2得

定理2.1設(shè)u=(ui,vj)為復(fù)合圖Pm[Pn]中的一個頂點(diǎn)，e(u)為頂點(diǎn)u的離心率，則有

定理2.2設(shè)e=uv為復(fù)合圖Pm[Pn]中一條邊，e(u),e(v)分別為頂點(diǎn)u和v的離心率，則有

證明當(dāng)m=2k+1時，即m為奇數(shù)時，

總之，無論m取偶數(shù)還是奇數(shù)，都有

定理2.3設(shè)e=uv為復(fù)合圖Pm[Pn]中一條邊,e(u),e(v)分別為頂點(diǎn)u和v的離心率,則有

證明當(dāng)m=2k+1時，即m為奇數(shù)時,

定理2.4設(shè)e=uv為復(fù)合圖Pm[Pn]中一條邊,e(u),e(v)分別為頂點(diǎn)u和v的離心率,則有

總之，無論m取偶數(shù)還是奇數(shù)，都有

2.2 笛卡爾積圖的Zagreb離心率指標(biāo)及非自中心數(shù)

引理2.2設(shè)圖G和H是簡單圖，則對于頂點(diǎn)(u,v)∈V(G×H),有

定理2.5設(shè)圖G和H是簡單圖，則笛卡爾積圖G×H的第一類Zagreb離心率指標(biāo)為

定理2.6設(shè)圖G和H是簡單圖，則笛卡爾積圖G×H的第二類Zagreb離心率指標(biāo)為

定理2.7設(shè)圖G和H是簡單圖，則笛卡爾積圖G×H的第三類Zagreb離心率指標(biāo)為

定理2.8設(shè)圖G和H是簡單圖，則笛卡爾積圖G×H的非自中心數(shù)為

這里δ(G,H)是一個關(guān)于G和H的對稱函數(shù).