MathDB

The Zagreb index inequality conjecture

About 15 years old · traced to

Let G=(V,E)G=(V,E) be a simple connected graph with n=∣V∣n=|V| vertices and m=∣E∣m=|E| edges. Its first and second Zagreb indices are

M1=∑i∈Vdi2,M2=∑(i,j)∈Edidj,M_1=\sum_{i\in V}d_i^2,\qquad M_2=\sum_{(i,j)\in E}d_i d_j,

where did_i is the degree of vertex ii. Zagreb index inequality conjecture. For all such graphs,

M1n⩽M2m,\frac{M_1}{n}\leqslant\frac{M_2}{m},

and the bound is tight for complete graphs. The conjecture was disproved for general connected graphs, but it was proven to hold for chemical graphs; this paper also identifies classes, such as subdivision graphs, for which it holds.

References

Primary source

Aleksandar Ilić and Dragan Stevanović, “On comparing Zagreb indices”, arXiv:1104.4262 (2011).

graph-invariantsgraph-theory
Posted

Progress summary

Refreshed
Claimed solved

The conjecture is false for general connected graphs, but it remains valid for several important restricted graph classes.

Hansen and Vukičević showed in 2007 that the proposed inequality fails for general graphs, although it holds for chemical graphs. Subsequent work established further positive cases and constructed connected counterexamples.

Known results

  • A connected counterexample has 4646 vertices and 110110 edges; counterexamples exist with any fixed number of cycles k≥2k \ge 2 (Hansen and Vukičević, 2007; subsequent work, 2011).
  • The inequality holds for trees, with equality only for stars, and for connected unicyclic graphs, with equality only for cycles (2011).
  • It holds for subdivision graphs, with equality exactly when the original graph is regular (2011).
  • If the degree sequence and degree-sum sequence are similarly ordered, the inequality holds; equality occurs exactly for regular or complete bipartite graphs (2022).

2025 structural counterexamples

A 2025 paper proves that, among graphs whose maximum and minimum degrees differ by at most 33, any counterexample must have minimum degree 22 and maximum degree 55. It also constructs infinitely many connected counterexamples with those degree bounds and order at least 218218, strengthening the known disproof rather than resolving a remaining positive conjecture.

Current status (as of September 2026): The general conjecture is settled negatively by connected counterexamples, while its validity remains established only for restricted classes and sufficient conditions; no claimed proof or AI-assisted resolution was found.

Sources

Solutions 0

No solutions have been posted yet.