A new conjecture on the inertia of graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915689230499840 |
|---|---|
| author | Akbari, Saieed Elphick, Clive Kumar, Hitesh Pragada, Shivaramakrishna Tang, Quanyu |
| author_facet | Akbari, Saieed Elphick, Clive Kumar, Hitesh Pragada, Shivaramakrishna Tang, Quanyu |
| contents | Let $G$ be a graph with adjacency matrix $A(G)$. We conjecture that \[2n^+(G) \le n^-(G)(n^-(G) + 1),\] where $n^+(G)$ and $n^-(G)$ denote the number of positive and negative eigenvalues of $A(G)$, respectively. This conjecture generalizes to all graphs the well-known absolute bound for strongly regular graphs. The conjecture also relates to a question posed by Torgašev. We prove the conjecture for special graph families, including line graphs and planar graphs, and provide examples where the conjecture is exact. We also conjecture that for any connected graph $G$, its line graph $L(G)$ satisfies $n^+(L(G)) \le n^-(L(G)) + 1$, and obtain partial results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_01163 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A new conjecture on the inertia of graphs Akbari, Saieed Elphick, Clive Kumar, Hitesh Pragada, Shivaramakrishna Tang, Quanyu Combinatorics 05C50, 05C76, 05E30 Let $G$ be a graph with adjacency matrix $A(G)$. We conjecture that \[2n^+(G) \le n^-(G)(n^-(G) + 1),\] where $n^+(G)$ and $n^-(G)$ denote the number of positive and negative eigenvalues of $A(G)$, respectively. This conjecture generalizes to all graphs the well-known absolute bound for strongly regular graphs. The conjecture also relates to a question posed by Torgašev. We prove the conjecture for special graph families, including line graphs and planar graphs, and provide examples where the conjecture is exact. We also conjecture that for any connected graph $G$, its line graph $L(G)$ satisfies $n^+(L(G)) \le n^-(L(G)) + 1$, and obtain partial results. |
| title | A new conjecture on the inertia of graphs |
| topic | Combinatorics 05C50, 05C76, 05E30 |
| url | https://arxiv.org/abs/2508.01163 |