Groupe d’études et de recherche en analyse des décisions

# Comparing Zagreb Indices of Cyclic Graphs

## Gilles Caporossi, Pierre Hansen et Damir Vukicevic

Given a graph G=(V,E), the first Zagreb index M1 is the sum of its vertices squared degrees and the second Zagreb index M2 is the sum of its edges products of degrees. Recently, there has been much interest in comparing M1 and M2 (and generalizations of them). The case of trees was handled in Vukicevic and Graovac (2008). In this paper, we consider the case of cyclic graphs and provide two best possible lower bounds on M2-M1 in terms of order and cyclicity of G. On the basis of some experiments with the system AutoGraphiX, it was conjectured that $M_1/n \leq M_2/m$. This was disproved in Hansen and Vukicevic (2007) both for disconnected and for connected graphs. However, it is true for chemical graphs. We show here that it still holds for unicyclic graphs but is not true in general for graphs with a larger number of independent cycles.

, 13 pages