On a lower bound for the Laplacian eigenvalues of a graph

If \(\mu_m\) and \(d_m\) denote, respectively, the \(m\)-th largest Laplacian eigenvalue and the \(m\)-th largest vertex degree of a graph, then \(\mu_m \geqslant d_m-m+2\). This inequality was conjectured by Guo in 2007 and proved by Brouwer and Haemers in 2008. Brouwer and Haemers gave several exa...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2017-07
Main Authors: Greaves, Gary R W, Munemasa, Akihiro, Peng, Anni
Format: Article
Language:English
Subjects:
Eigenvalues
Graphs
Lower bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:If \(\mu_m\) and \(d_m\) denote, respectively, the \(m\)-th largest Laplacian eigenvalue and the \(m\)-th largest vertex degree of a graph, then \(\mu_m \geqslant d_m-m+2\). This inequality was conjectured by Guo in 2007 and proved by Brouwer and Haemers in 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 \(\mu_m = d_m-m+2\). In particular we give a full classification of graphs with \(\mu_m = d_m-m+2 \leqslant 1\).
ISSN:2331-8422
DOI:10.48550/arxiv.1707.03221