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 $\lambda_N\unicode{x2A7E} \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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IOP Publishing
2025-01-01
|
| Series: | Journal of Physics: Complexity |
| Subjects: | |
| Online Access: | https://doi.org/10.1088/2632-072X/adcc71 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | For a graph with largest normalized Laplacian eigenvalue λ _N and (vertex) coloring number χ , it is known that $\lambda_N\unicode{x2A7E} \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 λ _N in terms of χ . Our findings provide insights into the connection between several properties of networks, such as their coloring number, their normalized Laplacian spectrum, and the existence of cut vertices. This has potential applications to the analysis of complex systems such as biological and chemical networks. |
|---|---|
| ISSN: | 2632-072X |