A characterization on graphs which achieve the upper bound for the largest Laplacian eigenvalue of graphs

Research output: Contribution to journalArticlepeer-review

36 Scopus citations

Abstract

Let G = (V, E) be a simple connected graph and λ1 (G) be the largest Laplacian eigenvalue of G. In this paper, we prove that: 1. λ1 (G) = d1 + d2, (d1 ≠ d2) if and only if G is a star graph, where d1, d 2 are the highest and the second highest degree, respectively. 2. λ1 (G) = max ⌈√2(du2+d um′u): u ∈ V⌉ if and only if G is a bipartite regular graph, where m′u = ∑v{d v-|Nu∩Nv|:uvE}, du denotes the degree of u and |Nu ∩ Nv| is the number of common neighbors of u and v. 3. λ1(G) ≤ max ⌈(d u+dv)+√(du-dv) 2+4mumv2: uv ∈ E⌉ with equality if and only if G is a bipartite regular graph or a bipartite semiregular graph, where du and mu denote the degree of u and the average of the degrees of the vertices adjacent to u, respectively.

Original languageEnglish
Pages (from-to)173-186
Number of pages14
JournalLinear Algebra and Its Applications
Volume376
Issue number1-3
DOIs
StatePublished - 1 Jan 2004
Externally publishedYes

Keywords

  • Graph
  • Laplacian matrix
  • Largest eigenvalue
  • Upper bound

Fingerprint

Dive into the research topics of 'A characterization on graphs which achieve the upper bound for the largest Laplacian eigenvalue of graphs'. Together they form a unique fingerprint.

Cite this