On a lower bound for the Laplacian eigenvalues of a graph

On a lower bound for the Laplacian eigenvalues of a graph

If μm and dm denote, respectively, the m-th largest Laplacian eigenvalue and the m-th largest vertex degree of a graph, then μm⩾dm−m+2. This inequality was conjectured by Guo (Linear Multilinear Algebra 55:93–102, 2007) and proved by Brouwer and Haemers (Linear Algebra Appl 429:2131–2135, 2008). Bro...

Full description

Saved in:
Bibliographic Details
Main Authors: Greaves, Gary Royden Watson, Munemasa, Akihiro, Peng, Anni
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2020
Subjects:
Science::Mathematics
Laplacian Eigenvalues
Degree Sequence
Online Access:https://hdl.handle.net/10356/144996
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary:If μm and dm denote, respectively, the m-th largest Laplacian eigenvalue and the m-th largest vertex degree of a graph, then μm⩾dm−m+2. This inequality was conjectured by Guo (Linear Multilinear Algebra 55:93–102, 2007) and proved by Brouwer and Haemers (Linear Algebra Appl 429:2131–2135, 2008). Brouwer and Haemers gave several examples of graphs achieving equality, but a complete characterisation was not given. In this paper we consider the problem of characterising graphs satisfying μm=dm−m+2. In particular we give a full classification of graphs with μm=dm−m+2⩽1.

Similar Items