Volume 36 • Number 1 • 2013   • Bipartite Graphs with the Maximal Value of the Second Zagreb Index Rongling Lang, Xiaole Deng and Hui Lu Abstract. The second Zagreb index of a graph $G$ is an adjacency-based topological index, which is defined as $\sum_{uv \in 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_2+n_1^2)$ time for a bipartite graph $B$ with a partition $|X|=n_1$ and $|Y|=n_2$. 2010 Mathematics Subject Classification: 05C35 Full text: PDF