History
Year:
-
Type:
Journal
Book
Article
Please fill in your query. A complete syntax description you will find on the General Help page.
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$.