Optimizing the Gutman Index: A Study of minimum Values Under Transformations of Graphs

Document Type : Original paper


1 Department of Mathematics, College of Sciences, University of Sharjah, Sharjah, UAE

2 Mathematical Sciences Department, College of Science, United Arab Emirates University, UAE.


The extremal Gutman index is a concept that studies the maximum or minimum value of the Gutman index for a particular class of graphs. This research area is concerned with finding the graphs that have the lowest possible Gutman index within a set of graphs that have been transformed in some way, such as by adding or removing edges or vertices. By understanding the graphs that have the lowest possible Gutman index, researchers can better understand the fundamental principles of graph stability and the role that different graph transformations play in affecting the overall stability of a graph. The research in this area is ongoing and continues to expand as new techniques and algorithms are developed. The findings from this research have the potential to have a significant impact on a wide range of fields and can lead to new and more effective ways of analyzing and understanding complex systems and relationships in a variety of applications. This paper focuses on the study of specific types of trees that are defined by fixed parameters and characterized based on their Gutman index. Specifically, we explore the structural properties of graphs that have the lowest Gutman index within these classes of trees. To achieve this, we utilize various graph transformations that either decrease or increase the Gutman index. By applying these transformations, we construct trees that satisfy the desired criteria.


Main Subjects

[1] A. Ahmad, A.N.A. Koam, and M. Azeem, Reverse-degree-based topological indices of fullerene cage networks, Molecular Physics 121 (2023), no. 14, Article ID: e2212533.
[2] P. Ali, S. Mukwembi, and S. Munyira, Degree distance and vertex-connectivity, Discrete Appl. Math. 161 (2013), no. 18, 2802–2811.
[3] P. Ali, S. Mukwembi, and S. Munyira, Degree distance and edge-connectivity, J. Australas. Combin. 60 (2014),
[4] V. Andova, D. Dimitrov, J. Fink, and R. ˇSkrekovski, Bounds on Gutman index, MATCH Commun. Math. Comput. Chem. 67 (2012), no. 2, 515–524.
[5] M. Arockiaraj, S.R.J. Kavitha, and K. Balasubramanian, Vertex cut method for degree and distance-based topological indices and its applications to silicate networks, J. Math. Chem. 54 (2016), no. 8, 1728–1747.
[6] A.T. Balaban, Topological and stereochemical molecular descriptors for databases useful in QSAR, similarity/dissimilarity and drug design, SAR and QSAR in Environmental Research 8 (1998), no. 1-2, 1–21.
[7] K. Balasubramanian, Integration of graph theory and quantum chemistry for structure-activity relationships, SAR and QSAR in Environmental Research 2 (1994), no. 1-2, 59–77.
[8] K. Balasubramanian, Mathematical and computational techniques for drug discovery: promises and developments, Current Topics in Medicinal Chemistry 18 (2018), no. 32, 2774–2799.
[9] K. Balasubramanian and S.P. Gupta, Quantum molecular dynamics, topological, group theoretical and graph theoretical studies of protein-protein interactions, Current Topics in Medicinal Chemistry 19 (2019), no. 6, 426–443.
[10] K.C. Das, G. Su, and L. Xiong, Relation between degree distance and Gutman index of graphs, MATCH Commun. Math. Comput. Chem. 76 (2016), no. 1, 221–232
[11] L. Feng, W. Liu, A. Ilić, and G. Yu, Degree distance of unicyclic graphs with given matching number, Graphs Combin. 29 (2013), no. 3, 449–462.
[12] I. Gutman, Degree-based topological indices, Croat. Chem. Acta 86 (2013), no. 4, 351–361.
[13] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, CRC press, Boca Raton, 1998.
[14] C. He, S. Li, and J. Tu, Edge-grafting transformations on the average eccentricity of graphs and their applications, Discret. Appl. Math. 238 (2018), no. 13, 95–105.
[15] H. Hua, Wiener and Schultz molecular topological indices of graphs with specified cut edges, MATCH Commun. Math. Comput. Chem. 61 (2009), no. 3, 643–651.
[16] R. Kazemi and L. Meimondari, Degree distance and Gutman index of increasing trees, Trans. Comb. 5 (2016), no. 2, 23–31.
[17] F. Koorepazan-Moftakhar, A.R. Ashrafi, O. Ori, and M.V. Putz, Topological invariants of nanocones and fullerenes, Current Organic Chem. 19 (2015), no. 3, 240–248.
[18] S. Li and X. Meng, Four edge-grafting theorems on the reciprocal degree distance of graphs and their applications, J. Comb. Optim. 30 (2015), no. 3, 468–488.
[19] S. Li, Y. Song, and H. Zhang, On the degree distance of unicyclic graphs with given matching number, Graphs Combin. 31 (2015), no. 6, 2261–2274.
[20] S. Li and H. Zhang, Some extremal properties of the multiplicatively weighted Harary index of a graph, J. Comb. Optim. 31 (2016), no. 3, 961–978.
[21] S. Mukwembi and S. Munyira, Degree distance and minimum degree, Bull. Aust. Math. Soc. 87 (2013), no. 2, 255–271.
[22] B.A. Rather, M. Aouchiche, M. Imran, and S. Pirzada, On arithmetic–geometric eigenvalues of graphs, Main Group Metal Chemistry 45 (2022), no. 1, 111–123.
[23] Z. Raza and A. Ali, Bounds on the Zagreb indices for molecular $(n, m)$-graphs, Int. J. Quantum Chem. 120 (2020), no. 18, Article ID: e26333.
[24] T. Réti, A. Ali, and I. Gutman, On bond-additive and atoms-pair-additive indices of graphs, Electron. J. Math. 2 (2021), 52–61.
[25] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947), no. 1, 17–20.
[26] K. Xu, S. Klavžar, K.C. Das, and J. Wang, Extremal $(n, m)$-graphs with respect to distance-degree-based topological indices, MATCH Commun. Math. Comput. Chem. 72 (2014), no. 3, 865–880.
[27] K. Xu, M. Liu, K.C. Das, I. Gutman, and B. Furtula, A survey on graphs extremal with respect to distance-based topological indices, MATCH Commun. Math. Comput. Chem. 71, no. 3, 461–508.