Comparing the Zagreb indices for graphs with small difference between the maximum and minimum degrees. (English)

Discrete Appl. Math. 157, No. 7, 1650-1654 (2009).

Summary: The first Zagreb index $M_{1}(G)$ and the second Zagreb index $M_{2}(G)$ of a (molecular) graph $G$ are defined as $M_{1}(G)=\sum _{u\in V(G)}(d(u))^{2}$ and $M_{2}(G)=\sum _{uv\in E(G)}d(u)d(v)$, where $d(u)$ denotes the degree of a vertex $u$ in $G$. The AutoGraphiX system [{\it M. Aouchiche} et al., Nonconvex Optimization and Its Applications 84, 281‒310 (2006; Zbl 1100.90052); {\it G. Caporossi} and {\it P. Hansen}, Discrete Math. 212, No. 1-2, 29‒44 (2000; Zbl 0947.90130); Discrete Math. 276, No. 1-3, 81‒94 (2004; Zbl 1031.05068)] conjectured that $M_{1}/n\leq M_{2}/m$ (where $n=|V(G)|$ and $m=|E(G)|)$ for simple connected graphs. {\it P. Hansen} and {\it D. Vukičević} [Croat. Chem. Acta 80, 165‒168 (2007)] proved that it is true for chemical graphs and it does not hold for all graphs. {\it D. Vukičević} and {\it A. Graovac} [MATCH Commun. Math. Comput. Chem. 57, No. 3, 587‒590 (2007; Zbl 1142.05313)] proved that it is also true for trees. In this paper, we show that $M_{1}/n\leq M_{2}/m$ holds for graphs with $\varDelta (G) - δ(G)\leq 2$ and characterize the extremal graphs, the proof of which implies the result in [Hansen and Vukičević, (loc. cit.)]. We also obtain the result that $M_{1}/n\leq M_{2}/m$ holds for graphs with $\varDelta (G) - δ(G)\leq 3$ and $δ(G)\neq 2$.