PII: S0893-9659(96)00071-7 The Szeged and the Wiener Index of Graphs

Abst rac t--The Szeged index Sz is a recently introduced graph invariant, having applications in chemistry. In this paper, a formula for the Szeged index of Cartesian product graphs is obtained and some other composite graphs are considered. We also prove that for all connected graphs, Sz is greater than or equal to the sum of distances between all vertices. A conjecture concerning the maximum value of Sz is put forward. Keywords--Distance in graphs, Wiener number, Szeged index, Graph products. 1