Bipartite graphs with the maximal value of the second Zagreb index

The second Zagreb index of a graph G is an adjacency-based topological index, which is defined as ∑ _uv∈E(G)(d(u)d(v)), where uv is an edge of G, d(u) is the degree of vertex u in G. In this paper, we consider the second Zagreb index for bipartite graphs. Firstly, we present a new definition of ordered bipartite graphs, and then give a necessary condition for a bipartite graph to attain the maximal value of the second Zagreb index. We also present an algorithm for transforming a bipartite graph to an ordered bipartite graph, which can be done in O(n ₂ +n ² ₁) time for a bipartite graph B with a partition {pipe}X{pipe} = n ₁ and {pipe}Y{pipe} = n ₂.