On comparing Zagreb indices

Original · EN

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 M₁ = ∑ᵢ ∈ ᵥ dᵢ² and M₂ = ∑₍ᵢ, ⱼ₎ ∈ ₑ dᵢ dⱼ, where dᵢ denote the degree of vertex i. Recently proposed conjecture M₁ / n M₂ / 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 M₁/n and M₂/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 M₁/n>M₂/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.