臺灣博碩士論文加值系統

維納指數是指一個圖形中所有點之間的距離總和，在圖論領域已經進行了廣泛的研究。雖然有不少的圖類，我們可以正確地算出它們的維納指數，可是就一般圖而言，計算維納指數是非常困難的工作。從文獻中，我們不難發現圖中的某一邊 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.

Contents

Abstract (in Chinese) i

Abstract (in English) ii

Acknowledgements iii

Contents iv

List of Figures v

List of Tables v

1 Introduction and preliminaries 1
1.1 Motivation .......................................1
1.2 Notations and terminologies ......................2
1.3 Known results ....................................4

2 The difference between W(G) and W(G-e) of composite graphs 7
2.1 Conditions for W(G-e) - W(G) = 1 .................7
2.2 Join graph and composition graph .................8
2.3 Cartesian product ...............................10
2.4 Combined product ................................17
2.5 Cluster, corona and unicyclic graph .............21

3 Upper bound of W(G-e) - W(G) 24

4 Concluding remarks 28

Reference 30

References

[1] X. An and B. Wu, The Wiener index of the kth power of a graph, Appl. Math. Lett. 21 (2008) 436-440.

[2] D. Bonchev and D. J. Klein, On the Wiener number of thorn trees, stars, rings, and rods, Croatica Chemica Acta 75 (2002) 613-620.

[3] F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, Redwood, (1990).

[4] A. A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: Theory and applications, Acta Appl. Math. 66 (2001) 211-249.

[5] R. C. Entringer, D. E. Jackson and D. A. Snyder, Distance in graphs, Czechoslovak Math. J. 26 (1976) 283-296.

[6] A. Graovac and T. Pisanski, On the Wiener index of a graph, J. Math. Chem. 8 (1991) 53-62.

[7] I. Gutman and Y.-N. Yeh. The sum of all distances in bipartite graphs, Math. Slovaca 45 (1995) 327-334.

[8] H. Hosoya, Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bull. Chem. Soc. Jpn. 4 (1971) 2332-2339.

[9] B. Mohar and T. Pisanski, How to compute the Wiener index of a graph, J. Math. Chem. 2 (1988) 267-277.

[10] K. Pattabiraman and P. Paulraja, Wiener index of the tensor product of a path and a cycle, Discuss. Math. Graph Theory 31 (2011) 737-751.

[11] I. Peterina and P. Z. Pletersek, Wiener index of strong product of graphs, Opuscula Math. 38 (2018), to appear.

[12] J. Plesnik, On the sum of all distances in a graph or digraph, J. Graph Theory 8 (1984) 1-21.

[13] B. E. Sagan, Y.-N. Yeh and P. Zhang, The Wiener polynomial of a graph, Int. J. Quantum Chem. 60 (1996) 959-969.

[14] L. Soltes, Transmission in graph: a bound and vertex removing, Math. Slovaka 41 (1991) 11-16.

[15] H. Wiener, Structural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947) 17-20.

[16] Y.-N. Yeh and I. Gutman, On the sum of all distances in composite graphs, Discrete Math. 135 (1994) 359-365.