Upper bounds for the reduced second zagreb index of graphs

Document Type : Research Paper

Authors

1 Department of Mathematics, Mongolian National University of Education, Baga toiruu-14, Ulaanbaatar, Mongolia

2 Department of Mathematics, National University of Mongolia, P.O.Box 187/46A, Ulaanbaatar, Mongolia

Abstract

The graph invariant $RM_2$‎, ‎known under the name reduced second Zagreb index‎, ‎is defined as $RM_2(G)=\sum_{uv\in E(G)}(d_G(u)-1)(d_G(v)-1)$‎, ‎where $d_G(v)$ is the degree of the vertex $v$ of the graph $G$‎. ‎In this paper‎, ‎we give a tight upper bound of $RM_2$ for the class of graphs of order $n$ and size $m$ with at least one dominating vertex‎. ‎Also‎, ‎we obtain sharp upper bounds on $RM_2$ for all graphs of order $n$ with $k$ dominating vertices and for all graphs of order $n$ with $k$ pendant vertices‎. ‎Finally‎, ‎we give a sharp upper bound on $RM_2$ for all $k$-apex trees of order $n$‎. ‎Moreover‎, ‎the corresponding extremal graphs are characterized‎.

Keywords

Main Subjects

References

[1] B. M. Ábrego, S. Fernández-Merchant, M. G. Neubauer and W. Watkins, Sum of squares of degrees in a graph, J.
Inequal. Pure Appl. Math., 10 (2009) 1–69.
[2] R. Ahlswede and G. O. H. Katona, Graphs with maximal number of adjacent pairs of edges, Acta Math. Hungar.,
32 (1978) 97–120.
[3] M. An and L. Xiong, Some results on the difference of the Zagreb indices of a graph, Bull. Aust. Math. Soc., 92
(2015) 177–186.
[4] M. Aghel, A. Erfanian and A. R. Ashrafi, On the first and second Zagreb indices of quasi unicyclic graphs, Trans.
Comb., 8 (2019) 29–39.
[5] A. Behtoei, Some relations and bounds for the general first Zagreb index, MATCH Commun. Math. Comput. Chem.,
81 (2019) 361–370.
[6] B. Bollobás, P. Erdős and A. Sarkar, Extremal graphs for weights, Discrete Math., 200 (1999) 5–19.
[7] B. Borovicanin, K. C. Das, B. Furtula and I. Gutman, Bounds for Zagreb Indices, MATCH Commun. Math. Comput.
Chem., 78 (2017) 17–100.
[8] L. Buyantogtokh, B. Horoldagva and K. C. Das, On reduced second Zagreb index, J. Combin. Opt., 39 (2020)
776–791.
[9] D. de Caen, An upper bound on the sum of squares of degrees in a graph, Discrete Math., 85 (1998) 245–248.
[10] K. C. Das, Maximizing the sum of the squares of the degrees of a graph, Discrete Math., 285 (2004) 57–66.
[11] K. C. Das and A. Akbar, On a conjecture about the second Zagreb index, Discrete Math. Lett., 2 (2019) 38–43.
[12] K. C. Das, I. Gutman and B. Horoldagva, Comparison between Zagreb indices and Zagreb coindices of trees, MATCH
Commun. Math. Comput. Chem., 68 (2012) 189–198.
[13] B. Furtula, I. Gutman and S. Ediz, On difference of Zagreb indices, Discrete Appl. Math., 178 (2014) 83–88.
[14] F. Gao and K. Xu, On the reduced second Zagreb index of graphs, Rocky Mountain J. Math., 50 (2020) 975–988.
[15] I. Gutman, B. Furtula and C. Elphick, Three new/old vertex-degree-based topological indices, MATCH Commun.
Math. Comput. Chem., 72 (2014) 617–632.
[16] I. Gutman and N. Trinajstić, Graph theory and molecular orbitals. Total π-electron energy of alternant hydrocar-
bons, Chem. Phys. Lett., 17 (1971) 535–538.
[17] X. He, S. Li and Q. Zhao, Sharp bounds on the reduced second Zagreb index of graphs with given number of cut
vertices, Discrete Appl. Math., 271 (2019) 49–63.
[18] B. Horoldagva, Relations between the first and second Zagreb indices of graphs, in: Bounds in Chemical Graph
Theory-Mainstreams (I. Gutman, B. Furtula, K. C. Das, E. Milovanovic, I. Milovanovic, eds.), Mathematical Chem-
istry Monographs, 20 (2017) 69–81.
[19] B. Horoldagva, L. Buyantogtokh and S. Dorjsembe, Difference of Zagreb indices and reduced second Zagreb index
of cyclic graphs with cut edges, MATCH Commun. Math. Comput. Chem., 78 (2017) 337–350.
[20] B. Horoldagva, L. Buyantogtokh, K. C. Das and S.-G. Lee, On general reduced second Zagreb index of graphs,
Hacet. J. Math. Stat., 48 (2019) 1046–1056.
[21] B. Horoldagva and K. C. Das, Sharp lower bounds for the Zagreb indices of unicyclic graphs, Turk. J. Math., 39
(2015) 595–603.
[22] B. Horoldagva and K.C. Das, On Zagreb indices of graphs, MATCH Commun. Math. Comput. Chem., 85 (2021)
295–301.
[23] B. Horoldagva, K. C. Das and T. Selenge, Complete characterization of graphs for direct comparing Zagreb indices,
Discrete Appl. Math., 215 (2016) 146–154.
[24] S. Ji and S. Wang, On the sharp lower bounds of Zagreb indices of graphs with given number of cut vertices, J.
Math. Anal. Appl., 458 (2018) 21–29.
[25] A. Martinez-Perez and J.M. Rodriguez, A unified approach to bounds for topological indices on trees and applica-
tions, MATCH Commun. Math. Comput. Chem., 82 (2019) 679–698.
[26] S. Nikolić, G. Kovačević, A. Milićević and N. Trinajstić, The Zagreb indices 30 years after, Croat. Chem. Acta, 76
(2003) 113–124.
[27] 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.
[28] T. Selenge and B. Horoldagva, Maximum Zagreb indices of k-apex trees, Korean J. Math., 23 (2015) 401–408.
[29] T. Selenge, B. Horoldagva and K. C. Das, Direct comparison of the variable Zagreb indices of cyclic graphs, MATCH
Commun. Math. Comput., 78 (2017) 351–360.
[30] H. Wang and S. Yuan, On the sum of squares of degrees and products of adjacent degrees, Discrete Math., 339
(2016) 1212–1220.
[31] K. Xu, K. C. Das and S. Balachandran, Maximizing the Zagreb indices of (n, m)-graphs, MATCH Commun. Math.
Comput. Chem., 72 (2014) 641–654.
[32] Y. Yao, M. Liu, K. C. Das and Y. Ye, Some extremal results for vertex-degree-based invariants, MATCH Commun.
Math. Comput. Chem., 81 (2019) 325–344.
Transactions on Combinatorics
Volume 10, Issue 3 - Serial Number 3
September 2021
Pages 137-148

Files

Cited by

History

  • Receive Date: 18 October 2020
  • Revise Date: 01 December 2020
  • Accept Date: 05 December 2020
  • Published Online: 01 September 2021

Share

How to cite

Statistics