Comparing the Zagreb indices for graphs with small difference between the maximum and minimum degrees

AbstractThe first Zagreb index M1(G) and the second Zagreb index M2(G) of a (molecular) graph G are defined as M1(G)=∑u∈V(G)(d(u))2 and M2(G)=∑uv∈E(G)d(u)d(v), where d(u) denotes the degree of a vertex u in G. The AutoGraphiX system [M. Aouchiche, J.M. Bonnefoy, A. Fidahoussen, G. Caporossi, P. Hansen, L. Hiesse, J. Lacheré, A. Monhait, Variable neighborhood search for extremal graphs. 14. The AutoGraphiX 2 system, in: L. Liberti, N. Maculan (Eds.), Global Optimization: From Theory to Implementation, Springer, 2005; G. Caporossi, P. Hansen, Variable neighborhood search for extremal graphs: 1 The AutoGraphiX system, Discrete Math. 212 (2000) 29–44; G. Caporossi, P. Hansen, Variable neighborhood search for extremal graphs. 5. Three ways to automate finding conjectures, Discrete Math. 276 (2004) 81–94] conjectured that M1/n≤M2/m (where n=|V(G)| and m=|E(G)|) for simple connected graphs. Hansen and Vukičević [P. Hansen, D. Vukičević, Comparing the Zagreb indices, Croat. Chem. Acta 80 (2007) 165–168] proved that it is true for chemical graphs and it does not hold for all graphs. Vukičević and Graovac [D. Vukičević, A. Graovac, Comparing Zagreb M1 and M2 indices for acyclic molecules, MATCH Commun. Math. Comput. Chem. 57 (2007) 587–590] proved that it is also true for trees. In this paper, we show that M1/n≤M2/m holds for graphs with Δ(G)−δ(G)≤2 and characterize the extremal graphs, the proof of which implies the result in [P. Hansen, D. Vukičević, Comparing the Zagreb indices, Croat. Chem. Acta 80 (2007) 165–168]. We also obtain the result that M1/n≤M2/m holds for graphs with Δ(G)−δ(G)≤3 and δ(G)≠2