Minimizing the Laplacian-energy-like of graphs (Q6618714)

Let \(G\) be a connected graph on \(n\) vertices, and denote the eigenvalues of its Laplacian matrix \(L(G)\) by \(\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n = 0\). The Laplacian-energy-like of \(G\) is \(\operatorname{LEL}(G):= \sum_{i=1}^{n}\sqrt{\lambda_i}\). The Laplacian-energy-like is a variation on the well-studied graph energy. The question addressed by this paper is: for given positive integers \(n\) and \(m\) with \(n-1\le m\le \binom{n}{2}\), which connected graph with \(n\) vertices and \(m\) edges minimizes the Laplacian-energy-like among all such graphs? The authors show, building on prior work of a number of authors, that for all \(n\) and \(m\) the unique connected graph on \(n\) vertices and \(m\) edges which minimizes the Laplacian-energy-like among all such graphs is the quasi-complete graph, which is defined as follows: let \(k\) and \(j\) be the unique integers such that \(m = (n-1) + \binom{k+1}{2} - j\), \(1\le j\le k\). Now, starting from the complete graph on the \(k+1\) vertices \(1, 2, \dots, k+1\), remove the \(j\) edges \((k-j+1, k+1), \dots, (k, k+1)\); add the vertices \(k+2, \dots, n-1, n\) to the graph; and finally, add the \(n-1\) edges \((1, n), \dots, (n-1, n)\) to the graph. This is the quasi-complete graph on \(n\) vertices and \(m\) edges.\N\NThe proof of the main theorem is given in Section 3, with background information on prior work and threshold graphs in Section 2. A threshold graph is a graph which is \(\{2K_2, C_4, P_4\}\)-free. Alternatively, threshold graphs may be constructed by an iterative process of adding isolated and dominating vertices starting from an empty graph. By previous work of \textit{D. Stevanović} [MATCH Commun. Math. Comput. Chem. 61, No. 2, 407--417 (2009; Zbl 1274.05304)], \textit{S.-C. Gong} et al. [Linear Algebra Appl. 631, 398--406 (2021; Zbl 1476.05114)] and \textit{Z. R. Bogdanowicz} [Discrete Math. 309, No. 10, 3074--3082 (2009; Zbl 1202.05021)], it is known that every connected graph on \(n\) vertices and \(m\) edges which minimizes the Laplacian-energy-like of a graph is a threshold graph. There is a certain Ferrers diagram that may be associated with any given threshold graph, and the authors use these Ferrers diagrams to reframe the question of minimizing the Laplacian-energy-like of a graph as a combinatorial question involving weighted Ferrers diagrams, which is fully analyzed in Section 3.