Let G be a simple graph of order n.The second Zagreb index of G is defined as M2(G)=∑ij∈E(G) didj,where di is the degree of the vertex i.Xu et al.(2014)proposed a conjecture related to the second Zagreb index:the quasi-complete graph has the maximum second Zagreb index among all the graphs having n vertices and m edges.With the aid of the properties of the Ferrers diagram in threshold graphs,we transform the above conjecture into an optimization problem in combinatorial matrix theory and provide an algebraic proof of the conjecture.
关键词
Zagreb指数/Ferrers表/门槛图/度
Key words
Zagreb index/Ferrers diagram/threshold graph/degree
维普
万方数据