Title: 透過刪邊來研究圖的維納指數
A Study of Wiener Index via Deleting Edges
Authors: 許純寧
Hsu, Chuen-Ning
Fu, Hung-Lin
Keywords: 維納指數;圖形上的距離;合成圖;連結圖;乘積圖;笛卡爾積圖;單環圖;Wiener index;distances of graph;join graph;composition graph;Cartesian (square) product;cluster (rooted product);corona;unicyclic graph
Issue Date: 2017
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.
URI: http://etd.lib.nctu.edu.tw/cdrfb3/record/nctu/#GT070452220
Appears in Collections:Thesis