טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentBougaev Yulia
SubjectThe Wiener Index of a Graph
DepartmentDepartment of Applied Mathematics
Supervisor Professor Emeritus Abraham Berman


Abstract



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.