Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.01207 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916465931714560 |
|---|---|
| author | Zhang, Wenqian |
| author_facet | Zhang, Wenqian |
| contents | Let $G$ be a graph with $n$ vertices and $m$ edges. The spectral radius $ρ(G)$ of $G$ is the largest eigenvalue of the adjacency matrix of $G$. As is well known, $ρ(G)\geq\frac{2m}{n}$ with equality if and only if $G$ is regular. To bound $ρ(G)-\frac{2m}{n}$, Nikiforov (2006) introduced the degree deviation of $G$ as $$s(G)=\sum_{1\leq i\leq n}|d_{i}-\frac{2m}{n}|,$$ where $d_{1},d_{2},\ldots,d_{n}$ are the degrees of the vertices of $G$. Nikiforov conjectured that $ρ(G)-\frac{2m}{n}\leq\sqrt{\frac{1}{2}s(G)}$ for sufficiently large $m$ and $n$. In this paper, we settle this conjecture without the assumption that $m$ and $n$ are large. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_01207 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A tight upper bound of spectral radius in terms of degree deviation Zhang, Wenqian Combinatorics Let $G$ be a graph with $n$ vertices and $m$ edges. The spectral radius $ρ(G)$ of $G$ is the largest eigenvalue of the adjacency matrix of $G$. As is well known, $ρ(G)\geq\frac{2m}{n}$ with equality if and only if $G$ is regular. To bound $ρ(G)-\frac{2m}{n}$, Nikiforov (2006) introduced the degree deviation of $G$ as $$s(G)=\sum_{1\leq i\leq n}|d_{i}-\frac{2m}{n}|,$$ where $d_{1},d_{2},\ldots,d_{n}$ are the degrees of the vertices of $G$. Nikiforov conjectured that $ρ(G)-\frac{2m}{n}\leq\sqrt{\frac{1}{2}s(G)}$ for sufficiently large $m$ and $n$. In this paper, we settle this conjecture without the assumption that $m$ and $n$ are large. |
| title | A tight upper bound of spectral radius in terms of degree deviation |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.01207 |