The Edge-Szeged Index and the PI Index of Benzenoid Systems in Linear Time

Abstract

The edge-Szeged index of a graph $G$ is defined as $S{z}_e(G)={\sum }_{e=uv\in E(G)}{m}_u(e)m_v(e)$, where $m_u(e)$ denotes the number of edges of $G$ whose distance to $u$ is smaller than the distance to $v$ and $m_v(e)$ denotes the number of edges of $G$ whose distance to $v$ is smaller than the distance to $u$. Similarly, the PI index is defined as $PI(G)={\sum }_{e=uv\in E(G)}(m_u(e)+m_v(e))$. In this paper it is shown how the problem of calculating the indices of a benzenoid system can be reduced to the problem of calculating weighted indices of three different weighted quotient trees. Furthermore, using these results, algorithms are established that, for a given benzenoid system $G$ with $m$ edges, compute the edge-Szeged index and the PI index of $G$ in $O(m)$ time. Moreover, it is shown that the results can also be applied to weighted benzenoid systems.

Cited by in corpus (5)

• The Szeged Index and the Wiener Index of Partial Cubes with Applications to Chemical Graphs
• Equivalence of the Generalized Zhang-Zhang Polynomial and the Generalized Cube Polynomial
• On the Steiner hyper-Wiener index of a graph
• The Edge-Wiener Index, the Szeged Indices and the PI Index of Benzenoid Systems in Sub-Linear Time
• On Extremal Graphs of Weighted Szeged Index