The Szeged and the Wiener index of graphs. (English) Zbl 0903.05020

Kalvžar, S.; Rajapakse, A.; Gutman, I.

Appl. Math. Lett. 9, No. 5, 45-49 (1996).

Summary: 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.

MSC:

05C12	Distance in graphs
05C90	Applications of graph theory

Keywords:

Wiener index; Szeged index; graph invariant; Cartesian product graphs; distances

References:

[1]	Gutman, I.; Yeh, Y. N.; Lee, S. L.; Luo, Y. L., Some recent results in the theory of the Wiener number, Indian J. Chem., 32A, 651-661 (1993)
[2]	Gutman, I., A formula for the Wiener number of trees and its extension to graphs containing cycles, Graph Theory Notes, 27, 9-15 (1994), New York
[3]	Dobrynin, A.; Gutman, I., On a graph invariant related to the sum of all distances in a graph, Publ. Inst. Math. (Beograd), 56, 18-22 (1994) · Zbl 0831.05026
[4]	Dobrynin, A.; Gutman, I., Solving a problem connected with distances in graphs, Graph Theory Notes, 28, 21-23 (1995), New York
[5]	Dobrynin, A. A.; Gutman, I.; Dömötör, G., A Wiener-type graph invariant for some bipartite graphs, Appl. Math. Lett., 8, 5, 57-62 (1995) · Zbl 0839.05037
[6]	Gutman, I.; Khadikar, P. V.; Rajput, P. V.; Karmarkar, S., The Szeged index of polyacenes, J. Serb. Chem. Soc., 60, 759-764 (1995)
[8]	Graovac, A.; Pisanski, T., On the Wiener index of a graph, J. Math. Chem., 8, 53-62 (1991)
[9]	Yeh, Y. N.; Gutman, I., On the sum of all distances in composite graphs, Discrete Math., 135, 359-365 (1994) · Zbl 0814.05033