Complexity of the Szeged index, edge orbits, and some nanotubical fullerenes

Abstract

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.

Keywords

• Szeged index
• Szeged complexity
• vertex-transitive graph
• edge-transitive graphs
• fullerene
• total eccentricity

References

1. [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. [2] Y. Alizadeh, Szeged dimension and $PI_v$ dimension of composite graphs, Iranian J. Math. Sci. Inform. 13, 45–57, 2018.
3. [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. [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. [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. [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. [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. [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. [9] D. Buset, Orbits on vertices and edges of finite graphs, Discrete Math. 57, 297–299, 1985.
10. [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. [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. [12] R.C. Entringer, D.E. Jackson and D.A. Snyder, Distance in graphs, Czechoslovak Math. J. 26, 283–296, 1976.
13. [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. [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. [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. [16] I. Gutman and B. Furtula (Eds.), Novel Molecular Structure Descriptors—Theory and Applications I, Univ. Kragujevac, Kragujevac, 2010.
17. [17] I. Gutman and B. Furtula (Eds.), Novel Molecular Structure Descriptors—Theory and Applications II, Univ. Kragujevac, Kragujevac, 2010.
18. [18] I. Gutman, K. Xu and M. Liu, A congruence relation for Wiener and Szeged indices, Filomat, 29, 1081–1083, 2015.
19. [19] M. Imran, A.Q Baig and H. Ali, On molecular topological properties of hex-derived networks, J. Chemometrics, 30, 121–129, 2016.
20. [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. [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. [22] S. Klavžar and M.J. Nadjafi-Arani, Wiener index versus Szeged index in networks, Discrete Appl. Math. 161, 1150–1153, 2013.
23. [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. [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. [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. [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. [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. [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. [29] S. Simić, I. Gutman and V. Baltić, Some graphs with extremal Szeged index, Math. Slovaca, 50, 1–15, 2000.
30. [30] H. Smith, L. Székely and H. Wang, Eccentricity sums in trees, Discrete Appl. Math. 207, 120–131, 2016.
31. [31] R. Todeschini and V. Consonni, Molecular Decriptors for Chemoinformatic, Wiley- VCH, Weinheim, 2009.
32. [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. [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.