On the Zagreb index inequality of graphs with prescribed vertex degrees
For a simple graph G G with n n vertices and m m edges, the inequality M1(G)/n?M2(G)/m M 1 ( G ) / n ? M 2 ( G ) / m , where M1(G) M 1 ( G ) and M2(G) M 2 ( G ) are the first and the second Zagreb indices of G G , is known as the Zagreb indices inequality. A set S S is good if for every graph whose degrees of vertices are in S S , 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 S S of cardinality s s is good, which requires O(s2logs) O ( s 2 log s ) time and O(s) O ( s ) space.
first zagreb index second zagreb index