兩類圖運算的Zagreb 離心率指標

阿斯牙·米吉提

（喀什大學數學與統計學院，新疆 喀什 844000）

0 引言

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

圖不變量是一個從圖的集合到實數的函數.在化學圖論中，圖不變量通常被稱為拓撲指標.在拓撲指標中，文獻[1]中引入的Zagreb 指標是最著名的，其中Gutman 和Trinajsti?研究了總π-電子能量對分子結構的依賴性，并在文獻[2]中作了進一步研究.第一類Zagreb 指標和第二類Zagreb指標分別被定義為

這兩個經典的拓撲指標反映了分子骨架的分支程[3].關于Zagreb 指標的各種結果見文獻[4-9].與第一類和第二類Zagreb 指標類似,Vuki?evic 和Hosseinazdeh[10]引入了Zagreb離心率指標，并定義

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

定義

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

定義

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

最近，又有一種新的圖的點的離心率指標被引入，其中有拓撲離心連通指標、離心距離和n類離心Zagreb 指標等.進一步，有Xu[11]等人引入了衡量圖的非自中心數，并定義

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

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

1 定義及引理

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

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

引理1.1[12]設G和H是圖,則有

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

（2）G×H是連通的當且僅當G與H都是連通的；

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

引理1.2[13]若復合圖G[?H]是連通當且僅當圖G和H是連通的,則有

2 主要結果及證明

2.1 復合圖的Zagreb 離心率指標及非自中心數

引理2.1設Pm和Pn分別為有m個頂點和有n個頂點的路,則對復合圖Pm[Pn]，有

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

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

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

證明當m=2k+1時，即m為奇數時，

總之，無論m取偶數還是奇數，都有

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

證明當m=2k+1時，即m為奇數時,

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

總之，無論m取偶數還是奇數，都有

2.2 笛卡爾積圖的Zagreb離心率指標及非自中心數

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

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

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

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

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

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