Complexity of the Szeged index, edge orbits, and some nanotubical fullerenes
Let $I$ be a summation-type topological index. The $I$-complexity $C_I(G)$ of a graph $G$ is the number of different contributions to $I(G)$ in its summation formula. In this paper the complexity $C_{Sz}(G)$ is investigated, where Sz is the well-studied Szeged index. Let $O_e(G)$ (resp. $O_v(G)$) be the number of edge (resp. vertex) orbits of $G$. While $C_{Sz}(G) \leq O_e(G)$ holds for any graph $G$, it is shown that for any $m\geq 1$ there exists a vertex-transitive graph $G_m$ with $C_{Sz}(G_m) = O_e(G_m) = m$. Also, for any $1\leq k\leq m+1$ there exists a graph $G_{m,k}$ with $C_{Sz}(G_{m,k}) = O_e(G_{m,k}) = m$ and $C_{W}(G_{m,k}) = O_v(G_{m,k}) = k$. The Sz-complexity is determined for a family of (5,0)-nanotubical fullerenes and the Szeged index is compared with the total eccentricity.
___
- [1] A. Abiad, B. Brimkov, A. Erey, L. Leshock, X. Martínez-Rivera, S. O, S.-Y. Song
and J. Williford, On the Wiener index, distance cospectrality and transmission-regular
graphs, Discrete Appl. Math. 230, 1–10, 2017.
- [2] Y. Alizadeh, Szeged dimension and $PI_v$ dimension of composite graphs, Iranian J.
Math. Sci. Inform. 13, 45–57, 2018.
- [3] Y. Alizadeh, V. Andova, S. Klavžar and R. Škrekovski, Wiener dimension: fundamen-
tal properties and (5,0)-nanotubical fullerenes, MATCH Commun. Math. Comput.
Chem. 72, 279–294, 2014.
- [4] Y. Alizadeh and S. Klavžar, Complexity of topological indices: The case of connective
eccentric index, MATCH Commun. Math. Comput. Chem. 76, 659–667, 2016.
- [5] Y. Alizadeh and S. Klavžar, On graphs whose Wiener complexity equals their order
and on Wiener index of asymmetric graphs, Appl. Math. Comput. 328, 113–118,
2018.
- [6] V. Andova, T. Došlić, M. Krnc, B. Lužar and R. Škrekovski, On the diameter and
some related invariants of fullerene graphs, MATCH Commun. Math. Comput. Chem.
68, 109–130, 2012.
- [7] M. Arockiaraj, J. Clement and K. Balasubramanian, Analytical expressions for topo-
logical properties of polycyclic benzenoid networks, J. Chemometrics, 30, 682–697,
2016.
- [8] M. Arockiaraj, J. Clement and A.J. Shalini, Variants of the Szeged index in certain
chemical nanosheets, Canad. J. Chem. 94, 608–619, 2016.
- [9] D. Buset, Orbits on vertices and edges of finite graphs, Discrete Math. 57, 297–299,
1985.
- [10] K.Ch. Das and M.J. Nadjafi-Arani, Comparison between the Szeged index and the
eccentric connectivity index, Discrete Appl. Math. 186, 74–86, 2015.
- [11] A.A. Dobrynin and I. Gutman, Solving a problem connected with distances in graphs,
Graph Theory Notes N. Y. 28, 21–23, 1995.
- [12] R.C. Entringer, D.E. Jackson and D.A. Snyder, Distance in graphs, Czechoslovak
Math. J. 26, 283–296, 1976.
- [13] M. Goubko and O. Miloserdov, Simple alcohols with the lowest normal boiling point
using topological indices, MATCH Commun. Math. Comput. Chem. 75, 29–56, 2016.
- [14] S. Gupta, M. Singh and A.K. Madan, Connective eccentricity index: a novel topo-
logical descriptor for predicting biological activity, J. Mol. Graph. Model. 18, 18–25,
2000.
- [15] I. Gutman, A formula for the Wiener number of trees and its extension to graphs
containing cycles, Graph Theory Notes N. Y. 27, 9–15, 1994.
- [16] I. Gutman and B. Furtula (Eds.), Novel Molecular Structure Descriptors—Theory
and Applications I, Univ. Kragujevac, Kragujevac, 2010.
- [17] I. Gutman and B. Furtula (Eds.), Novel Molecular Structure Descriptors—Theory
and Applications II, Univ. Kragujevac, Kragujevac, 2010.
- [18] I. Gutman, K. Xu and M. Liu, A congruence relation for Wiener and Szeged indices,
Filomat, 29, 1081–1083, 2015.
- [19] M. Imran, A.Q Baig and H. Ali, On molecular topological properties of hex-derived
networks, J. Chemometrics, 30, 121–129, 2016.
- [20] P.V. Khadikar, S. Karmarkar, V.K. Agrawal, J. Singh, A. Shrivastava, I. Lukovits
and M.V. Diudea, Szeged index - applications for drug modeling, Lett. Drug Des.
Discov. 2, 606–624, 2005.
- [21] S. Klavžar, D. Azubha Jemilet, I. Rajasingh, P. Manuel and N. Parthiban, Gen-
eral Transmission Lemma and Wiener complexity of triangular grids, Appl. Math.
Comput. 338, 115–122, 2018.
- [22] S. Klavžar and M.J. Nadjafi-Arani, Wiener index versus Szeged index in networks,
Discrete Appl. Math. 161, 1150–1153, 2013.
- [23] S. Klavžar and M.J. Nadjafi-Arani, Improved bounds on the difference between the
Szeged index and the Wiener index of graphs, European J. Combin. 39, 148–156,
2014.
- [24] S. Klavžar, A. Rajapakse and I. Gutman, The Szeged and the Wiener index of graphs,
Appl. Math. Lett. 9, 45-49, 1996.
- [25] S. Li and H. Zhang, Proofs of three conjectures on the quotients of the (revised) Szeged
index and the Wiener index and beyond, Discrete Math. 340, 311–324, 2017.
- [26] M.J. Nadjafi-Arani, H. Khodashenas and A.R. Ashrafi, On the differences between
Szeged and Wiener indices of graphs, Discrete Math. 311, 2233–2237, 2011.
- [27] M.J. Nadjafi-Arani, H. Khodashenas and A.R. Ashrafi, Graphs whose Szeged and
Wiener numbers differ by 4 and 5, Math. Comput. Modelling, 55, 1644–1648, 2012.
- [28] F. Shafiei, M. Pashm Froush and F. Dialamehpour, QSPR study on benzene deriva-
tives to some physicochemical properties by using topological indices, Iranian J. Math.
Chem. 7, 93–110, 2016.
- [29] S. Simić, I. Gutman and V. Baltić, Some graphs with extremal Szeged index, Math.
Slovaca, 50, 1–15, 2000.
- [30] H. Smith, L. Székely and H. Wang, Eccentricity sums in trees, Discrete Appl. Math.
207, 120–131, 2016.
- [31] R. Todeschini and V. Consonni, Molecular Decriptors for Chemoinformatic, Wiley-
VCH, Weinheim, 2009.
- [32] K. Xu, K.Ch. Das and H. Liu, Some extremal results on the connective eccentricity
index of graphs, J. Math. Anal. Appl. 433, 803–817, 2016.
- [33] H. Zhang, S. Li and L. Zhao, On the further relation between the (revised) Szeged
index and the Wiener index of graphs, Discrete Appl. Math. 206, 152–164, 2016.