Springe zum Hauptinhalt
Fakultät für Mathematik
Fakultät für Mathematik
Christoph Helmberg, Vilmar Trevisan: Threshold Graphs of Maximal Laplacian Energy

Christoph Helmberg, Vilmar Trevisan: Threshold Graphs of Maximal Laplacian Energy


Author(s):
Christoph Helmberg
Vilmar Trevisan
Title:
Christoph Helmberg, Vilmar Trevisan: Threshold Graphs of Maximal Laplacian Energy
Electronic source:
application/pdf
Preprint series:
Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 02, 2014
Mathematics Subject Classification:
    05C50 []
    05C35 []
Abstract:
The Laplacian energy of a graph sums up the absolute values of the differences of average degree and eigenvalues of the Laplace 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 $i$-th 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.
Keywords:
Laplacian Energy, Laplacian spectrum, threshold graph, conjugate degree sequence
Language:
English
Publication time:
01/2014