The relationship between the negative inertia index of graph $G$ and its girth $g$ and diameter $d$
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910286009597952 |
|---|---|
| author | Xu, Songnian Zhen, Wenhao Wong, Dein |
| author_facet | Xu, Songnian Zhen, Wenhao Wong, Dein |
| contents | Let $G$ be a simple connected graph. We use $n(G)$, $p(G)$, and $η(G)$ to denote the number of negative eigenvalues, positive eigenvalues, and zero eigenvalues of the adjacency matrix $A(G)$ of $G$, respectively. In this paper, we prove that $2n(G)\geq d(G) + 1$ when $d(G)$ is odd, and $n(G) \geq \lceil \frac{g}{2}\rceil - 1$ for a graph containing cycles, where $d(G)$ and $g$ are the diameter and girth of the graph $G$, respectively. Furthermore, we characterize the extremal graphs for the cases of $2n(G) = d(G) + 1$, $n(G) = \lceil \frac{g}{2}\rceil$, and $n(G) = \lceil \frac{g}{2}\rceil - 1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_02680 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The relationship between the negative inertia index of graph $G$ and its girth $g$ and diameter $d$ Xu, Songnian Zhen, Wenhao Wong, Dein Spectral Theory Combinatorics O5C50 Let $G$ be a simple connected graph. We use $n(G)$, $p(G)$, and $η(G)$ to denote the number of negative eigenvalues, positive eigenvalues, and zero eigenvalues of the adjacency matrix $A(G)$ of $G$, respectively. In this paper, we prove that $2n(G)\geq d(G) + 1$ when $d(G)$ is odd, and $n(G) \geq \lceil \frac{g}{2}\rceil - 1$ for a graph containing cycles, where $d(G)$ and $g$ are the diameter and girth of the graph $G$, respectively. Furthermore, we characterize the extremal graphs for the cases of $2n(G) = d(G) + 1$, $n(G) = \lceil \frac{g}{2}\rceil$, and $n(G) = \lceil \frac{g}{2}\rceil - 1$. |
| title | The relationship between the negative inertia index of graph $G$ and its girth $g$ and diameter $d$ |
| topic | Spectral Theory Combinatorics O5C50 |
| url | https://arxiv.org/abs/2312.02680 |