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.