Spectral threshold dominance, Brouwer's conjecture and maximality of Laplacian energy

DOI10.1016/J.LAA.2016.09.029zbMATH Open1348.05124arXiv1604.07867OpenAlexW2342574437WikidataQ123197465 ScholiaQ123197465MaRDI QIDQ332628FDOQ332628

Authors: Christoph Helmberg, Vilmar Trevisan 

Publication date: 8 November 2016

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: The Laplacian energy of a graph is the sum of the distances of the eigenvalues of the Laplacian matrix of the graph to the graph's average degree. The maximum Laplacian energy over all graphs on $n$ nodes and $m$ edges is conjectured to be attained for threshold graphs. We prove the conjecture to hold for graphs with the property that for each $k$ there is a threshold graph on the same number of nodes and edges whose sum of the $k$ largest Laplacian eigenvalues exceeds that of the $k$ largest Laplacian eigenvalues of the graph. We call such graphs spectrally threshold dominated. These graphs include split graphs and cographs and spectral threshold dominance is preserved by disjoint unions and taking complements. We conjecture that all graphs are spectrally threshold dominated. This conjecture turns out to be equivalent to Brouwer's conjecture concerning a bound on the sum of the $k$ largest Laplacian eigenvalues.

Full work available at URL: https://arxiv.org/abs/1604.07867

Recommendations

• Threshold graphs of maximal Laplacian energy
• On Laplacian eigenvalues of graphs and Brouwer's conjecture
• On the sum of the Laplacian eigenvalues of a graph and Brouwer's conjecture
• On Brouwer's conjecture for the sum of \(k\) largest Laplacian eigenvalues of graphs
• Upper bounds for the sum of Laplacian eigenvalues of a graph and Brouwer's conjecture

zbMATH Keywords

Laplacian energythreshold graphBrouwer's conjectureGrone-Merris-Bbai theorem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal problems in graph theory (05C35) Distance in graphs (05C12)

Cites Work

• On a conjecture for the sum of Laplacian eigenvalues
• On the sum of the Laplacian eigenvalues of a tree
• Bounding the sum of the largest Laplacian eigenvalues of graphs
• Upper bounds for the sum of Laplacian eigenvalues of graphs
• On the sum of Laplacian eigenvalues of graphs
• Threshold graphs of maximal Laplacian energy
• Maximum Laplacian energy among threshold graphs
• The Grone-Merris conjecture
• The Laplacian energy of threshold graphs and majorization
• Degree maximal graphs are Laplacian integral
• Title not available (Why is that?)

Cited In (12)

• On the sum of \(k\) largest Laplacian eigenvalues of a graph and clique number
• Upper bounds for the sum of Laplacian eigenvalues of a graph and Brouwer’s conjecture
• Brouwer's conjecture for the Cartesian product of graphs
• Constraints on Brouwer's Laplacian spectrum conjecture
• The Laplacian energy of threshold graphs and majorization
• Improved results on Brouwer's conjecture for sum of the Laplacian eigenvalues of a graph
• Threshold graphs of maximal Laplacian energy
• Further developments on Brouwer's conjecture for the sum of Laplacian eigenvalues of graphs
• Maximum Laplacian energy among threshold graphs
• On Laplacian eigenvalues of graphs and Brouwer's conjecture
• On the sum of the k largest absolute values of Laplacian eigenvalues of digraphs
• On Zagreb index, signless Laplacian eigenvalues and signless Laplacian energy of a graph

This page was built for publication: Spectral threshold dominance, Brouwer's conjecture and maximality of Laplacian energy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q332628)