Complexity of the Szeged index, edge orbits, andsome nanotubical fullerenes

LetIbe a summation-type topological index. TheI-complexityCI(G)of a graphGisthe number of different contributions toI(G)in its summation formula. In this paper thecomplexity$C_{Sz}$(G)is investigated, whereSzis the well-studied Szeged index. Let$O_e$(G)(resp.$O_v$(G)) be the number of edge (resp. vertex) orbits ofG. While$C_{Sz}$(G)≤$O_e$(G)holds for any graphG, it is shown that for anym≥1there exists a vertex-transitive graphGmwithCSz(Gm) =Oe(Gm) =m. Also, for any1≤k≤m+ 1there exists a graphGm,kwith$C_{Sz}$($Gm,_k$) =$O_e$($Gm_k$) =mandCW($Gm,_k$) =Ov($Gm,_k$) =k. The Sz-complexity isdetermined for a family of (5,0)-nanotubical fullerenes and the Szeged index is comparedwith the total eccentricity.

PDF

___

[1]A. Abiad, B. Brimkov, A. Erey, L. Leshock, X. Martínez-Rivera, S. O, S.-Y. Songand J. Williford,On the Wiener index, distance cospectrality and transmission-regulargraphs, Discrete Appl. Math.230, 1–10, 2017.
[2]Y. Alizadeh,Szeged dimension andP Ivdimension 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 connectiveeccentric index, MATCH Commun. Math. Comput. Chem.76, 659–667, 2016.
[5]Y. Alizadeh and S. Klavžar,On graphs whose Wiener complexity equals their orderand 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 andsome 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 certainchemical 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 theeccentric 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, CzechoslovakMath. J.26, 283–296, 1976.
[13]M. Goubko and O. Miloserdov,Simple alcohols with the lowest normal boiling pointusing 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 graphscontaining cycles, Graph Theory Notes N. Y.27, 9–15, 1994.
[16]I. Gutman and B. Furtula (Eds.),Novel Molecular Structure Descriptors—Theoryand Applications I, Univ. Kragujevac, Kragujevac, 2010.
[17]I. Gutman and B. Furtula (Eds.),Novel Molecular Structure Descriptors—Theoryand 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-derivednetworks, J. Chemometrics,30, 121–129, 2016.
[20]P.V. Khadikar, S. Karmarkar, V.K. Agrawal, J. Singh, A. Shrivastava, I. Lukovitsand 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 theSzeged 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) Szegedindex 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 betweenSzeged 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 andWiener 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 eccentricityindex 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) Szegedindex and the Wiener index of graphs, Discrete Appl. Math.206, 152–164, 2016.