On the Zagreb index inequality of graphs with prescribed vertex degrees

For a simple graph GG with nn vertices and mm edges, the inequality M1(G)/n≤M2(G)/mM1(G)/n≤M2(G)/m, where M1(G)M1(G) and M2(G)M2(G) are the first and the second Zagreb indices of GG, is known as the Zagreb indices inequality. A set SS is good if for every graph whose degrees of vertices are in SS, the inequality holds. We characterize that an interval [a,a+n][a,a+n] is good if and only if a≥n(n−1)2 or [a,a+n]=[1,4][a,a+n]=[1,4]. We also present an algorithm that decides if an arbitrary set SS of cardinality ss is good, which requires O(s2logs)O(s2logs) time and O(s)O(s) space.