Abstract
The first and the second Zagreb indices of a graph G are defined as \(M_1(G)= \sum _{v\in V_G}d_v^2 \) and \( M_2(G)= \sum _{uv\in E_G}d_ud_v\), where \(d_v,\, d_u\) are the degrees of vertices \(v,\, u\) in G. The difference of Zagreb indices of G is defined as \(\Delta M(G)=M_2(G)-M_1(G)\). A cactus is a connected graph in which every block is either an edge or a cycle. Let \(\mathscr {C}_{n,k}\) be the set of all n-vertex cacti with k pendant vertices and let \(\mathscr {C}_n^r\) be the set of all n-vertex cacti with r cycles. In this paper, the sharp upper bound on \(\Delta M(G)\) of graph G among \(\mathscr {C}_{n,k}\) (resp. \(\mathscr {C}_n^r\)) is established. Combining the results in Furtula et al. (Discrete Appl Math 178:83–88, 2014) and our results obtained in the current paper, sharp upper bounds on \(\Delta M(G)\) of n-vertex cacti and n-vertex unicyclic graphs are determined, respectively. All the extremal graphs are characterized.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
An MQ, Xiong LM (2015) Some results on the difference of the Zagreb indices of a graph. Bull Aust Math Soc 92(2):177–186
Balaban AT, Motoc I, Bonchev D, Mekenyan O (1983) Topological indices for structure-activity correlations. Top Curr Chem 114:21–55
Bondy JA, Murty USR (2008) Graph theory. Springer, Springer GTM 244
Borovićanin B, Furtula B (2016) On extremal Zagreb indices of trees with given domination number. Appl Math Comput 279:208–218
Borovićanin B, Das KCh, Furtula B, Gutman I (2017) Bounds for Zagreb indices. MATCH Commun Math Comput Chem 78:17–100
Caporossi G, Hansen P (2000) Variable neighborhood search for extremal graphs. 1. The AutoGraphiX system. Discrete Math 212:29–44
Caporossi G, Hansen P (2004) Variable neighborhood search for extremal graphs. 5. Three ways to automate finding conjectures. Discrete Math 276:81–94
Caporossi G, Hansen P, Vukičević D (2010) Comparing Zagreb indices of cyclic graphs. MATCH Commun Math Comput Chem 63(2):441–451
Feng YQ, Hu X, Li SC (2010) On the extremal Zagreb indices of graphs with cut edges. Acta Appl Math 110(2):667–684
Furtula B, Gutman I, Ediz S (2014) On difference of Zagreb indices. Discrete Appl Math 178:83–88
Gutman I (2013) Degree-based topological indices. Croat Chem Acta 86:351–361
Gutman I, Das KC (2004) The first Zagreb index 30 years after. MATCH Commun Math Comput Chem 50:83–92
Gutman I, Trinajstić N (1972) Graph theory and molecular Total orbitals. \(\pi \)-electron energy of alternant hydrocarbons. Chem Phys Lett 179:535–538
Gutman I, Ruščić B, Trinajstić N, Wilcox CF (1975) Graph theory and molecular orbitals. XII. Acyclic polyenes. J Phys Chem 62:3399–3405
Hansen P, Vukičević D (2007) Comparing the Zagreb indices. Croat Chem Acta 80:165–168
He WH, Li H, Xiao SF (2017) On the minimum Kirchhoff index of graphs with a given vertex \(k\)-partiteness and edge \(k\)-partiteness. Appl Math Comput 315:313–318
Horoldagva B, Das KC, Selenge T (2016) Complete characterization of graphs for direct comparing Zagreb indices. Discrete Appl Math 215:146–154
Horoldagva B, Buyantogtokh L, Dorjsembe S (2017) Difference of Zagreb indices and reduced second Zagreb index of cyclic graphs with cut edges. MATCH Commun Math Comput Chem 78:337–350
Hou AL, Li SC, Song LZ, Wei B (2011) Sharp bounds for Zagreb indices of maximal outerplanar graphs. J Comb Optim 22(2):252–269
Li SC, Zhang MJ (2011) Sharp upper bounds for Zagreb indices of bipartite graphs with a given diameter. Appl Math Lett 24(2):131–137
Li SC, Zhao Q (2011) Sharp upper bounds on Zagreb indices of bicyclic graphs with a given matching number. Math Comput Model 54(11–12):2869–2879
Li SC, Zhou HB (2010) On the maximum and minimum Zagreb indices of graphs with connectivity at most \(k\). Appl Math Lett 23(2):128–132
Milošević M, Réti T, Stevanović D (2012) On the constant difference of Zagreb indices. MATCH Commun Math Comput Chem 68:157–168
Nikolić S, Kovačević G, Miličević A, Trinajstić N (2003) The Zagreb indices 30 years after. Croat Chem Acta 76:113–124
Sah A, Sawhney M (2018) On the discrepancy between two Zagreb indices. Discrete Math 341(9):2575–2589
Selenge T-A, Horoldagva B, Das KC (2017) Direct comparison of the variable Zagreb indices of cyclic graphs. MATCH Commun Math Comput Chem 78(2):351–360
Vetrík T, Balachandran S (2018) General multiplicative Zagreb indices of trees. Discrete Appl Math 247:341–351
Wang H, Yuan S (2016) On the sum of squares of degrees and products of adjacent degrees. Discrete Math 339:1212–1220
Yuan WG, Zhang XD (2015) The second Zagreb indices of graphs with given degree sequence. Discrete Appl Math 185:230–238
Zhao Q, Li SC (2010a) Sharp bounds for the Zagreb indices of bicyclic graphs with \(k\)-pendant vertices. Discrete Appl Math 158(17):1953–1962
Zhao Q, Li SC (2010b) On the maximum Zagreb indices of graphs with \(k\) cut vertices. Acta Appl Math 111(1):93–106
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
S.L. acknowledges the financial support from the National Natural Science Foundation of China (Grant Nos. 11671164, 11271149).
Rights and permissions
About this article
Cite this article
Li, S., Zhang, L. & Zhang, M. On the extremal cacti of given parameters with respect to the difference of zagreb indices. J Comb Optim 38, 421–442 (2019). https://doi.org/10.1007/s10878-019-00391-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-019-00391-4