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(n2+n21) time for a bipartite graph B with a partition ∣X∣ = n1 and ∣Y∣ = n2. [ABSTRACT FROM AUTHOR]