On comparing Zagreb indices

Abstract

Let G = (V, E) be a simple graph with n = |V| vertices and m = |E| edges. The first and second Zagreb indices are among the oldest and the most famous topological indices, defined as M1 = Σiεv di2and M2 = Σ(i,j)εE d 1d2, where d1 denote the degree of vertex i. Recently proposed conjecture M1/n ≤ M2/m has been proven to hold for trees, unicyclic graphs and chemical graphs, while counterexamples were found for both connected and disconnected graphs. Our goal is twofold, both in favor of a conjecture and against it. Firstly, we show that the expressions M1/n and M2/m have the same lower and upper bounds, which attain equality for and only for regular graphs. We also establish sharp lower bound for variable first and second Zagreb indices. Secondly, we show that for any fixed number k > 2, there exists a connected graph with k cycles for which M1/n > M2/m holds, effectively showing that the conjecture cannot hold unless there exists some kind of limitation on the number of cycles or the maximum vertex degree in a graph. In particular, we show that the conjecture holds for subdivision graphs.