|M.Sc Student||Bougaev Yulia|
|Subject||The Wiener Index of a Graph|
|Department||Department of Applied Mathematics||Supervisor||Professor Emeritus Abraham Berman|
The thesis deals with a graph theoretical index-the Wiener index. For a connected graph G the Wiener index W(G) is defined as the sum of distances between all unordered pairs of vertices in the graph G. If G is disconnected, then .
The Wiener index was introduced by H. Wiener in 1947 and has been studied by many authors. The thesis contains a detailed survey of known results. Several formulas for computing the Wiener index of a graph and some bounds for it are given. In particular, the relation between the Wiener index of a graph and its Laplacian eigenvalues and some results for the Wiener index of line graphs are described.
The thesis contains original results about the Wiener index. Let G-v be the graph obtained from a graph G by deleting a vertex v. For a general graph G with n vertices and for some graph invariant we define the function called the deck ratio of . We show that if is vertex-increasing ( ) [respectively, if is vertex-decreasing ( )], then [respectively, ]. For the deck ratio of the Wiener index, that can be defined only for l-connected graphs, l>1, we obtained upper and lower bounds
Graphs for which the upper bound is achieved are called self-repairing graphs.
Let g(n) be the smallest number of edges that makes any 2-connected graph with n vertices, self-repairing. We prove that
We also show that if the Cartesian product of 2-connected graphs , , G is a self-repairing graph if and only if every , is a self-repairing graph.