On general reduced second Zagreb index of graphs

Abstract

Recently, Furtula et al. [B. Furtula, I. Gutman, S. Ediz, On difference of Zagreb indices, Discrete Appl. Math., 2014] introduced a new vertex-degree-based graph invariant "reduced second Zagreb index" in chemical graph theory. Here we generalize the reduced second Zagreb index (call "general reduced second Zagreb index"), denoted by $GRM_{\alpha}(G)$ and is defined as: $GRM_\alpha(G)=\sum_{uv\in E(G)}(d_G(u)+\alpha)(d_G(v)+\alpha),$ where $\alpha$ is any real number and $d_G(v)$ is the degree of the vertex $v$ of $G$. Let $\mathcal{G}_n^k$ be the set of connected graphs of order $n$ with $k$ cut edges. In this paper, we study some properties of $GRM_\alpha(G)$ for connected graphs $G$. Moreover, we obtain the sharp upper bounds on $GRM_\alpha(G)$ in $\mathcal{G}_n^{k}$ for $\alpha\geq-1/2$ and characterize the extremal graphs.

Keywords

• Connected graph,Zagreb indices,general reduced second Zagreb index,cut edge,maximum degree

References

1. [1] B. Bollobás, P. Erdös, and Sarkar, A. Extremal graphs for weights, Discrete Math. 200, 5–19, 1999.
2. [2] B. Borovicanin and T.A. Lampert, On the maximum and minimum Zagreb indices of trees with a given number of vertices of maximum degree, MATCH Commun. Math. Comput. Chem. 74, 81–96, 2015.
3. [3] G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs. 5. Three ways to automate finding conjectures, Discrete Math. 276, 81–94, 2004.
4. [4] G. Caporossi, P. Hansen, and D. Vukičević, Comparing Zagreb indices of cyclic graphs, MATCH Commun. Math. Comput. Chem. 63, 441–451, 2010.
5. [5] S. Chen and W. Liu,Extremal Zagreb indices of graphs with a given number of cut edges, Graphs and Combinatorics 30, 109–118, 2014.
6. [6] K.C. Das, Maximizing the sum of the squares of the degrees of a graph, Discrete Math. 285, 57–66, 2004.
7. [7] K.C. Das and I. Gutman, Some properties of the second Zagreb index, MATCH Commun. Math. Comput. Chem. 52, 103–112, 2004.
8. [8] K.C. Das, I. Gutman, and B. Horoldagva, Comparison between Zagreb indices and Zagreb coindices of trees, MATCH Commun. Math. Comput. Chem. 68, 189–198, 2012.

9. [9] C. Elphick and T. Reti, On the relations between the Zagreb indices, clique numbers and walks in graphs, MATCH Commun. Math. Comput. Chem. 74, 19–34, 2015.
10. [10] Y. Feng, X. Hu, and S. Li, On the extremal Zagreb indices of graphs with cut edges, Acta Appl. Math. 110, 667–684, 2010.
11. [11] Y. Feng, X. Hu, and S. Li, Erratum to: On the extremal Zagreb indices of graphs with cut edges, Acta Appl. Math. 110, 685, 2010.
12. [12] B. Furtula, I. Gutman, and S. Ediz, On difference of Zagreb indices, Discrete Appl. Math. 178, 83–88, 2014.
13. [13] I. Gutman, B. Furtula, and C. Elphick, Three new/old vertex degree-based topological indices, MATCH Commun. Math. Comput. Chem. 72, 617–682, 2014.
14. [14] I. Gutman, B. Ruščić, N. Trinajstić, and C.F. Wilcox, Graph theory and molecular orbitals, XII. Acyclic polyenes, J. Chem. Phys. 62, 3399–3405, 1975.
15. [15] I. Gutman and N. Trinajstić, Graph theory and molecular orbitals. Total $\pi$-electron energy of alternant hydrocarbons, Chem. Phys. Lett. 17 535–538, 1971.
16. [16] P. Hansen and D. Vukičević, Comparing the Zagreb indices, Croat. Chem. Acta 80, 165–168, 2007.
17. [17] 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, 337–349, 2017.
18. [18] B. Horoldagva and K.C. Das, On comparing Zagreb indices of graphs, Hacettepe J. of Math. and Stat., 41, 223–230, 2012.
19. [19] B. Horoldagva, K.C. Das, and T. Selenge, Complete characterization of graphs for direct comparing Zagreb indices, Discrete Appl. Math. 215, 146–154, 2016.
20. [20] B. Horoldagva and S.-G. Lee, Comparing Zagreb indices for connected graphs, Discrete Appl. Math. 158, 1073–1078, 2010.
21. [21] U.N. Peled, R. Petreschi, and A. Sterbini, $(n,e)$-graphs with maximum sum of squares of degrees, J. Graph Theory 31, 283–295, 1999.
22. [22] T. Selenge and B. Horoldagva, Maximum Zagreb indices in the class of k-apex trees, Korean J. Math. 23, 401–408, 2015.
23. [23] http://math3.skku.ac.kr
24. [24] D. Stevanović and M. Milanič, Improved inequality between Zagreb indices of trees, MATCH Commun. Math. Comput. Chem. 68, 147–156, 2012.
25. [25] L. Sun and T. Chen, Comparing the Zagreb indices for graphs with small difference between the maximum and minimum degrees, Discrete. Appl. Math. 157, 1650–1654, 2009.
26. [26] D. Vukičević and A. Graovac, Comparing Zagreb $M_1$ and $M_2$ indices for acyclic molecules, MATCH Commun. Math. Comput. Chem. 57, 587–590, 2007.
27. [27] H. Wang and S. Yuan, On the sum of squares of degrees and products of adjacent degrees, Discrete Math. 339, 1212–1220, 2016.