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 language | English |
|---|---|
| Pages (from-to) | 173-186 |
| Number of pages | 14 |
| Journal | Linear Algebra and Its Applications |
| Volume | 376 |
| Issue number | 1-3 |
| DOIs | |
| State | Published - 1 Jan 2004 |
| Externally published | Yes |
Keywords
- Graph
- Laplacian matrix
- Largest eigenvalue
- Upper bound