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!
|
| _version_ | 1849715462131154944 |
|---|---|
| author | Lies Beers Raffaella Mulas |
| author_facet | Lies Beers Raffaella Mulas |
| author_sort | Lies Beers |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-d92a53850e5849da8d2cafba2c59ba4a |
| institution | DOAJ |
| issn | 2632-072X |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IOP Publishing |
| record_format | Article |
| series | Journal of Physics: Complexity |
| spelling | doaj-art-d92a53850e5849da8d2cafba2c59ba4a2025-08-20T03:13:22ZengIOP PublishingJournal of Physics: Complexity2632-072X2025-01-016202500610.1088/2632-072X/adcc71At the end of the spectrum: chromatic bounds for the largest eigenvalue of the normalized LaplacianLies Beers0https://orcid.org/0009-0003-7905-5804Raffaella Mulas1https://orcid.org/0000-0003-4995-6479Vrije Universiteit Amsterdam , Amsterdam, The NetherlandsVrije Universiteit Amsterdam , Amsterdam, The NetherlandsFor 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.https://doi.org/10.1088/2632-072X/adcc711-sumcoloring numberlargest eigenvaluenormalized Laplacian |
| spellingShingle | Lies Beers Raffaella Mulas At the end of the spectrum: chromatic bounds for the largest eigenvalue of the normalized Laplacian Journal of Physics: Complexity 1-sum coloring number largest eigenvalue normalized Laplacian |
| title | At the end of the spectrum: chromatic bounds for the largest eigenvalue of the normalized Laplacian |
| title_full | At the end of the spectrum: chromatic bounds for the largest eigenvalue of the normalized Laplacian |
| title_fullStr | At the end of the spectrum: chromatic bounds for the largest eigenvalue of the normalized Laplacian |
| title_full_unstemmed | At the end of the spectrum: chromatic bounds for the largest eigenvalue of the normalized Laplacian |
| title_short | At the end of the spectrum: chromatic bounds for the largest eigenvalue of the normalized Laplacian |
| title_sort | at the end of the spectrum chromatic bounds for the largest eigenvalue of the normalized laplacian |
| topic | 1-sum coloring number largest eigenvalue normalized Laplacian |
| url | https://doi.org/10.1088/2632-072X/adcc71 |
| work_keys_str_mv | AT liesbeers attheendofthespectrumchromaticboundsforthelargesteigenvalueofthenormalizedlaplacian AT raffaellamulas attheendofthespectrumchromaticboundsforthelargesteigenvalueofthenormalizedlaplacian |