Multiplicative Zagreb Indices and Extremal Complexity of Line Graphs

Document Type : Research Paper

Author

University of Zagreb Faculty of Civil Engineering‎, ‎Zagreb‎, ‎Croatia \\ Faculty of Information Studies‎, ‎Novo Mesto‎, ‎Slovenia

Abstract

‎The number of spanning trees of a graph $G$ is called the complexity of $G$‎. It is known that the complexity of the line graph of a given graph $G$ can‎ be computed as the sum over all spanning trees of $G$ of contributions‎ ‎which depend on various types of products of degrees of vertices of $G$‎. ‎We interpret the contributions in terms of three types of multiplicative‎ Zagreb indices‎, ‎obtaining simple and compact expressions for the complexity of‎ ‎line graphs of graphs with low cyclomatic numbers‎. ‎As an application‎, ‎we‎ determine the unicyclic graphs whose line graphs have the smallest and the‎ largest complexity‎.

Keywords

Main Subjects


[1] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Macmillan Press, New York, 1976.
[2] F. Harary, Graph Theory, Addison-Wesley Publishing Company, Boston, 1969.
[3] L. W. Beineke, Characterizations of derived graphs, J. Combinatorial Theory 9 (1970) 129–135, https://doi.org/10.1016/S0021-9800(70)80019-9.
[4] R. Todeschini and V. Consonni, Handbook of Molecular Descriptors, Wiley–VCH, Weinheim, 2009.
[5] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947) 17–20, https://doi.org/10.1021/ja01193a005.
[6] J. R. Platt, Influence of neighbour bonds on additive bond properties in paraffins, J. Chem. Phys. 15 (1947) 419–420, https://doi.org/10.1063/1.1746554.
[7] M. Gordon and G. R. Scantlebury, Non-random polycondensation: statistical theory of the substitution effect, Trans. Faraday Soc. 60 (1964) 604–621, https://doi.org/10.1039/TF9646000604.
[8] J. R. Platt, Prediction of isomeric differences in paraffin properties, J. Phys. Chem. 56 (1952) 328–336, https://doi.org/10.1021/j150495a009.
[9] I. Gutman and N. Trinajstic, Graph theory and molecular orbitals. Total - electron energy of alternant hydrocarbons, Chem. Phys. Lett. 17 (1972) 535–538, https://doi.org/10.1016/0009-2614(72)85099-1.
[10] I. Gutman, On the origin of two degree–based topological indices, Bull. Acad. Serbe Sci. Arts (Cl. Sci. Math. Natur.) 146 (2014) 39–52.
[11] V. Nikiforov, The sum of squares of degrees: sharp asymptotics, Discrete Math. 307 (2007) 3187–3193, https://doi.org/10.1016/j.disc.2007.03.019.
[12] U. N. Peled, R. Petreschi and A. Sterbini, (n; e)-Graphs with maximum sum of squares of degrees, J. Graph Theory 31 (1999) 283–295.
[13] D. de Caen, An upper bound on the sum of squares of degrees in a graph, Discrete Math. 185 (1998) 245–248, https://doi.org/10.1016/S0012-365X(97)00213-6.
[14] T. Došlic, B. Furtula, A. Graovac, I. Gutman, S. Moradi and Z. Yarahmadi, On vertexdegree- based molecular structure descriptors, MATCH Commun. Math. Comput. Chem. 66 (2011) 613–626.
[15] R. Todeschini, D. Ballabio and V. Consonni, Novel molecular descriptors based on functions of new vertex degrees, in I. Gutman and B. Furtula (Eds.), Novel Molecular Structure Descriptors -Theory and Applications I, Kragujevac, University of Kragujevac (2010) 73–100.
[16] R. Todeschini and V. Consonni, New local vertex invariants and molecular descriptors based on functions of the vertex degrees, MATCH Commun. Math. Comput. Chem. 64 (2010) 359–372.
[17] M. Eliasi, A. Iranmanesh and I. Gutman, Multiplicative versions of first Zagreb index, MATCH Commun. Math. Comput. Chem. 68 (2012) 217–230.
[18] K. Xu. and K. Ch. Das, Trees, unicyclic, and bicyclic graphs extremal with respect to multiplicative sum Zagreb index, MATCH Commun. Math. Comput. Chem. 68 (2012) 257–272.
[19] H. Narumi and M. Katayama, Simple topological index. A newly devised index characterizing the topological nature of structural isomers of saturated hydrocarbons, Memoirs Faculty Engin. Hokkaido Univ. 16 (1984) 209–214.
[20] M. A. Hosseinzadeh, A. Iranmanesh and T. Došlic, On the Narumi-Katayama index of composite graphs, Croat. Chem. Acta 86 (2013) 503–508, https://doi.org/10.5562/cca2329.
[21] H. Gong and X. Jin, A simple formula for the number of spanning trees of line graphs, J. Graph Theory 88 (2018) 294–301, https://doi.org/10.1002/jgt.22212.
[22] F. Dong and W. Yan, Expression for the number of spanning trees of line graphs of arbitrary connected graphs, J. Graph Theory 85 (2017) 74–93, https://doi.org/10.1002/jgt.22048.
[23] W. Yan, On the number of spanning trees of some irregular line graphs, J. Combin. Theory A 120 (2013) 1642–1648, https://doi.org/10.1016/j.jcta.2013.06.005.
[24] M. Ghorbani, M. Songhori and I. Gutman, Modified Narumi-Katayama index, Kragujevac J. Sci. 34 (2012) 57–64.
Volume 15, Issue 1
Special Issue Dedicated to the memory of Professor Ali Reza Ashrafi (University of Kashan, I.R. Iran), who was the creator and the Editor-in-Chief of IJMC for 14 years.
March 2024
Pages 7-16