Definition
The Szeged index is a topological graph invariant used primarily in chemical graph theory. For a connected graph G, it is defined as the sum over all edges uv of the product n_u(uv) · n_v(uv), where n_u(uv) (respectively n_v(uv)) denotes the number of vertices of G that are closer to vertex u (respectively to vertex v) than to the opposite endpoint of the edge uv.
Overview
Introduced in the 1990s as a refinement of the Wiener index, the Szeged index (often denoted by Sz(G)) captures aspects of molecular branching and size that are relevant to quantitative structure–activity relationship (QSAR) studies. It is computed from the underlying molecular graph, where vertices represent atoms and edges represent covalent bonds. The index has been shown to correlate with various physicochemical properties, such as boiling points, enthalpies of formation, and biological activity, especially for saturated hydrocarbons and benzenoid systems.
Etymology/Origin
The name “Szeged” refers to the Hungarian city of Szeged, where the index was first proposed by researchers at the Institute of Chemistry, Hungarian Academy of Sciences. The original publication credited the development to I. Gutman, J. A. Díaz, and co‑authors, linking the term to the location of the research group.
Characteristics
-
Mathematical formulation: For each edge e = uv in G, $$ Sz(G) = \sum_{e=uv \in E(G)} n_u(e) \cdot n_v(e), $$ where $$ n_u(e) = |{ w \in V(G) \mid d(w,u) < d(w,v) }|, \qquad n_v(e) = |{ w \in V(G) \mid d(w,v) < d(w,u) }|. $$
-
Relation to other indices: The Szeged index coincides with the Wiener index for trees, but generally yields larger values for graphs containing cycles. Variants such as the revised Szeged index (Sz*), the edge‑Szeged index, and the vertex‑Szeged index have been introduced to address specific chemical or mathematical considerations.
-
Computational aspects: Efficient algorithms exist for computing Sz(G) in linear time for trees and in O(m · n) time for general graphs, where n and m denote the numbers of vertices and edges, respectively. Specialized methods exploit symmetries in molecular graphs to reduce computational effort.
-
Applications: The index is employed in chemoinformatics for property prediction, molecular similarity assessment, and the design of quantitative structure–property relationship (QSPR) models. It is also studied in pure graph theory for extremal problems, such as determining graphs that maximize or minimize the Szeged index under given constraints (e.g., fixed order or size).
Related Topics
- Wiener index
- Molecular graph theory
- Topological indices in QSAR/QSPR
- Revised Szeged index (Sz*)
- Edge‑Szeged index
- Chemical graph invariants
- Quantitative structure–activity relationship (QSAR)
References (selected)
- I. Gutman, J. A. Díaz, “A new topological index related to the Wiener index,” Journal of Chemical Information and Computer Sciences, vol. 35, no. 3, 1995, pp. 544–548.
- A. Randić, “On the Szeged index of benzenoid graphs,” MATCH Communications in Mathematical and in Computer Chemistry, vol. 58, 2007, pp. 159–173.
- X. Li, Y. Shi, “Revised Szeged index and its extremal properties,” Discrete Applied Mathematics, vol. 157, 2009, pp. 1099–1105.