Threshold graphs of maximal Laplacian energy

The Laplacian energy of a graph is defined as the sum of the absolute values of the differences of average degree and eigenvalues of the Laplacian matrix of the graph. This spectral graph parameter is upper bounded by the energy obtained when replacing the eigenvalues with the conjugate degree sequence of the graph, in which the ith number counts the nodes having degree at least i. Because the sequences of eigenvalues and conjugate degrees coincide for the class of threshold graphs, these are considered likely candidates for maximizing the Laplacian energy over all graphs with given number of nodes. We do not answer this open problem, but within the class of threshold graphs we give an explicit and constructive description of threshold graphs maximizing this spectral graph parameter for a given number of nodes, for given numbers of nodes and edges, and for given numbers of nodes, edges and trace of the conjugate degree sequence in the general as well as in the connected case. In particular this positively answers the conjecture that the pineapple maximizes the Laplacian energy over all connected threshold graphs with given number of nodes. (C) 2015 Elsevier B.V. All rights reserved.