Abstract
The Laplacian spread of a graph G with n vertices is defined to be sL(G)= μ1(G)-μ n-1(G), where μ1(G), μn-1(G) are the largest and the second smallest Laplacian eigenvalues of G, respectively. It is conjectured that sL(G)≤n-1. In this paper, we first establish a new sharp upper bound for sL(G), and then use it to prove that the conjecture is true for t-quasi-regular graphs when t≤ √n-3+2/n. We also present some other partial solutions for this conjecture; in particular, we show that the conjecture holds for K3-free graphs. Finally, we give several sharp lower bounds for sL(G) as well.
| Original language | English |
|---|---|
| Pages (from-to) | 245-260 |
| Number of pages | 16 |
| Journal | Linear Algebra and Its Applications |
| Volume | 505 |
| DOIs | |
| State | Published - 15 Sep 2016 |
Keywords
- K-free graphs
- Laplacian spread
- Lower bound
- t-quasi-regular graphs
- Upper bound