At the end of the spectrum: Chromatic bounds for the largest eigenvalue of the normalized Laplacian
Lies Beers and Raffaella Mulas
Abstract
For a graph with largest normalized Laplacian eigenvalue \(\lambda_N\) and (vertex) coloring number \(\chi\), it is known that \(\lambda_N\geq \chi/(\chi-1)\). Here we prove properties of graphs for which this bound is sharp, and we study the multiplicity of \(\chi/(\chi-1)\). We then describe a family of graphs with largest eigenvalue \(\chi/(\chi-1)\). We also study the spectrum of the \(1\)-sum of two graphs (also known as graph joining or coalescing), with a focus on the maximal eigenvalue. Finally, we give upper bounds on \(\lambda_N\) in terms of \(\chi\).
At the end of the spectrum: Chromatic bounds for the largest eigenvalue of the normalized Laplacian
For a graph with largest normalized Laplacian eigenvalue $λ_N$ and (vertex) coloring number $χ$, it is known that $λ_N\geq χ/(χ-1)$. Here we prove properties of graphs for which this bound is sharp, and we study the multiplicity of $χ/(χ-1)$. We then describe a family of graphs with largest eigenvalue $χ/(χ-1)$. We also study the spectrum of the $1$-sum of two graphs (also known as graph joining or coalescing), with a focus on the maximal eigenvalue. Finally, we give upper bounds on $λ_N$ in terms of $χ$.
Lies Beers