The sum of squares of degrees of bipartite graphs (Q6061154)

This article concerns bipartite graphs that are maximal in the following sense. For any graph \(G\) of vertices \(v_1, v_2, \ldots, v_n\), let \(s(G) = \sum_{i=1}^n \text{ degree}(v_i)^2\). Call a subgraph \(G\) of \(K_{l,m}\) ``maximal'' if, for all subgraphs \(H\) of \(K_{l,m}\) of the same size as \(G\), \(s(G) \geq s(H)\). Letting the \(\mathcal{G}(e; l, m)\) be the set of all subgraphs of \(K_{l,m}\) of size \(e\), where \(l \leq m\), and letting \(q = \lfloor e/m \rfloor\) and \(p = e \!\mod m\), the maximal graphs are each of one of four forms: \(K_{q+1,m-1}\), \(K_{q+1,m} - K_{1,m-p}\), \(K_{q+p,m} - K_{p.m-1}\), or \(K_{q+1,m} - K_{m-p,1}\). And the maximal value of \(s(G)\) over all \(G \in \mathcal{G}\) is \(q m^2 + p^2 + p(q + 1)^2 + (m - p)^2\). To obtain these results, the paper starts with a lemma stating that a maximal bipartite graph has an adjacency matrix that, with an appropriate permutation of vertices, represents a Ferrers diagram of a partition.