透過刪邊來研究圖的維納指數

Abstract

維納指數是指一個圖形中所有點之間的距離總和，在圖論領域已經進行了廣泛的研究。雖然有不少的圖類，我們可以正確地算出它們的維納指數，可是就一般圖而言，計算維納指數是非常困難的工作。從文獻中，我們不難發現圖中的某一邊 e 扮演重要角色，也就是說能算去掉 e 前後的差值以及去掉邊之後的維納指數，就可以正確算出圖的維納指數。在本論文中，我們首先對特殊的合成圖，如連結圖、合成圖及乘積圖等做研究，算出可能的差值，最後就一般圖估計這變化的差值的上界。

Let G be a connected graph and d_{G}(u,v) denote the distance between two vertices u and v in V(G). Then the Wiener index of G denoted by W(G) is the total sum of all distances between two vertices in V(G), i.e. W(G) = Σ_{{x,y}⊆V(G)}d_G(x,y). Even there are quite a few classes of graphs G, W(G) is known. But, in general, computing W(G) is very difficult. From the literature, we observe that if we can obtain W(G-e) for certain e∈E(G) and the difference between W(G) and W(G-e), then we have W(G). Therefore, it is interesting to find the difference mentioned above. In this thesis, we first consider several types of composite graphs G such as join graphs, composition graphs and product graphs, and find the difference between W(G) and W(G-e) for all edges e as long as G-e is connected. Furthermore, an estimation of the upper bound on the difference for general graphs in obtained.