Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On a Lower Bound for the Laplacian Eigenvalues of a Graph

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

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 (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 \(\mu _m = d_m-m+2\). In particular we give a full classification of graphs with \(\mu _m = d_m-m+2 \leqslant 1\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Brouwer, A.E., Haemers, W.H.: A lower bound for the Laplacian eigenvalues of a graph—proof of a conjecture by Guo. Linear Algebra Appl. 429, 2131–2135 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  2. Brouwer, A.E., Haemers, W.H.: Spectra of Graphs. Springer, New York (2012)

    Book  MATH  Google Scholar 

  3. Grone, R., Merris, R.: The Laplacian spectrum of a graph II. SIAM J. Discrete Math. 7, 221–229 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  4. Guo, J.-M.: On the third largest Laplacian eigenvalue of a graph. Linear Multilinear Algebra 55, 93–102 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  5. Li, J.-S., Pan, Y.-L.: A note on the third second largest eigenvalue of the Laplacian matrix of a graph. Linear Multilinear Algebra 48, 117–121 (2000)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Physical and Mathematical Sciences, Nanyang Technological University, 21 Nanyang Link, Singapore, 637371, Singapore

    Gary R. W. Greaves

  2. Research Center for Pure and Applied Mathematics, Graduate School of Information Sciences, Tohoku University, Sendai, 980-8579, Japan

    Akihiro Munemasa

  3. School of Mathematical Sciences, Tongji University, 1239 Siping Road, Shanghai, People’s Republic of China

    Anni Peng

Authors
  1. Gary R. W. Greaves
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Akihiro Munemasa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Anni Peng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Akihiro Munemasa.

Additional information

G.R.W.G. was at Tohoku University while this work took place and was supported by JSPS KAKENHI; Grant Number: 26.03903.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Greaves, G.R.W., Munemasa, A. & Peng, A. On a Lower Bound for the Laplacian Eigenvalues of a Graph. Graphs and Combinatorics 33, 1509–1519 (2017). https://doi.org/10.1007/s00373-017-1835-y

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-017-1835-y

Keywords

Mathematics Subject Classification

Search

Navigation