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