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

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.


05C12 Distance in graphs
05C90 Applications of graph theory
Full Text: DOI

Online Encyclopedia of Integer Sequences:

Szeged index of the grid graph P_n X P_n.


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.