Comparing Zagreb indices for almost all graphs

Abstract

It was conjectured in literature that the inequality M1(G)/n ≤ M2(G)/m holds for all simple graphs, where M1(G) and M2(G) are the first and the second Zagreb index. By further research it was proven that the inequality holds for several graph classes such as chemical graphs, trees, unicyclic graphs and subdivided graphs, but that generally it does not hold since counter examples have been established in several other graph classes. So, the conjecture generally does not hold. Given the behavior of graphs satisfying the conjecture to some general graph operations it was further conjectured that the inequality might hold for almost all simple graphs. In this paper we will prove that this conjecture is true, by proving that the probability of a random graph G on n vertices to satisfy the inequality tends to 1 as n tends to infinity.