Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2404.09268 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910409775120384 |
|---|---|
| author | Esmailpour, Aryan Madani, Sara Saeedi Kiani, Dariush |
| author_facet | Esmailpour, Aryan Madani, Sara Saeedi Kiani, Dariush |
| contents | Let $G$ be a graph, and let $λ(G)$ denote the smallest eigenvalue of $G$. First, we provide an upper bound for $λ(G)$ based on induced bipartite subgraphs of $G$. Consequently, we extract two other upper bounds, one relying on the average degrees of induced bipartite subgraphs and a more explicit one in terms of the chromatic number and the independence number of $G$. In particular, motivated by our bounds, we introduce two graph invariants that are of interest on their own. Finally, special attention goes to the investigation of the sharpness of our bounds in various classes of graphs as well as the comparison with an existing well-known upper bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_09268 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Combinatorial upper bounds for the smallest eigenvalue of a graph Esmailpour, Aryan Madani, Sara Saeedi Kiani, Dariush Combinatorics 05C50 Let $G$ be a graph, and let $λ(G)$ denote the smallest eigenvalue of $G$. First, we provide an upper bound for $λ(G)$ based on induced bipartite subgraphs of $G$. Consequently, we extract two other upper bounds, one relying on the average degrees of induced bipartite subgraphs and a more explicit one in terms of the chromatic number and the independence number of $G$. In particular, motivated by our bounds, we introduce two graph invariants that are of interest on their own. Finally, special attention goes to the investigation of the sharpness of our bounds in various classes of graphs as well as the comparison with an existing well-known upper bound. |
| title | Combinatorial upper bounds for the smallest eigenvalue of a graph |
| topic | Combinatorics 05C50 |
| url | https://arxiv.org/abs/2404.09268 |