標題: 透過刪邊來研究圖的維納指數A Study of Wiener Index via Deleting Edges 作者: 許純寧傅恆霖Hsu, Chuen-NingFu, Hung-Lin應用數學系所 關鍵字: 維納指數;圖形上的距離;合成圖;連結圖;乘積圖;笛卡爾積圖;單環圖;Wiener index;distances of graph;join graph;composition graph;Cartesian (square) product;cluster (rooted product);corona;unicyclic graph 公開日期: 2017 摘要: 維納指數是指一個圖形中所有點之間的距離總和，在圖論領域已經進行了廣泛的研究。雖然有不少的圖類，我們可以正確地算出它們的維納指數，可是就一般圖而言，計算維納指數是非常困難的工作。從文獻中，我們不難發現圖中的某一邊 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. URI: http://etd.lib.nctu.edu.tw/cdrfb3/record/nctu/#GT070452220http://hdl.handle.net/11536/141038 Appears in Collections: Thesis