Extremal values for the square energies of graphs
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929515957059584 |
|---|---|
| author | Zhang, Shengtong |
| author_facet | Zhang, Shengtong |
| contents | Let $G$ be a graph with $n$ non-isolated vertices and $m$ edges. The positive / negative square energies of $G$, denoted $s^+(G)$ / $s^-(G)$, are defined as the sum of squares of the positive / negative eigenvalues of the adjacency matrix $A_G$ of $G$. In this work, we provide several new tools for studying square energy encompassing semi-definite optimization, graph operations, and surplus. Using our tools, we prove the following results on the extremal values of $s^{\pm}(G)$ with a given number of vertices and edges.
1. We have $\min(s^+(G), s^-(G)) \geq n - γ\geq \frac{n}{2}$, where $γ$ is the domination number of $G$. This verifies a conjecture of Elphick, Farber, Goldberg and Wocjan up to a constant, and proves a weaker version of this conjecture introduced by Elphick and Linz.
2. We have $s^+(G) \geq m^{6/7 - o(1)}$ and $s^-(G) = Ω(m^{1/2})$, with both exponents being optimal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_15504 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Extremal values for the square energies of graphs Zhang, Shengtong Combinatorics Spectral Theory Let $G$ be a graph with $n$ non-isolated vertices and $m$ edges. The positive / negative square energies of $G$, denoted $s^+(G)$ / $s^-(G)$, are defined as the sum of squares of the positive / negative eigenvalues of the adjacency matrix $A_G$ of $G$. In this work, we provide several new tools for studying square energy encompassing semi-definite optimization, graph operations, and surplus. Using our tools, we prove the following results on the extremal values of $s^{\pm}(G)$ with a given number of vertices and edges. 1. We have $\min(s^+(G), s^-(G)) \geq n - γ\geq \frac{n}{2}$, where $γ$ is the domination number of $G$. This verifies a conjecture of Elphick, Farber, Goldberg and Wocjan up to a constant, and proves a weaker version of this conjecture introduced by Elphick and Linz. 2. We have $s^+(G) \geq m^{6/7 - o(1)}$ and $s^-(G) = Ω(m^{1/2})$, with both exponents being optimal. |
| title | Extremal values for the square energies of graphs |
| topic | Combinatorics Spectral Theory |
| url | https://arxiv.org/abs/2409.15504 |