An Optimization Approach to Degree Deviation and Spectral Radius
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912161388822528 |
|---|---|
| author | Rautenbach, Dieter Werner, Florian |
| author_facet | Rautenbach, Dieter Werner, Florian |
| contents | For a finite, simple, and undirected graph $G$ with $n$ vertices and average degree $d$, Nikiforov introduced the degree deviation of $G$ as $s=\sum_{u\in V(G)}\left|d_G(u)-d\right|$. Provided that $G$ has largest eigenvalue $λ$, minimum degree at least $δ$, and maximum degree at most $Δ$, where $0\leqδ<d<Δ<n$, we show $$s\leq \frac{2n(Δ-d)(d-δ)}{Δ-δ} \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mbox{and}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, λ\geq \begin{cases} \frac{d^2n}{\sqrt{d^2n^2-s^2}} & \mbox{, if } s\leq \frac{dn}{\sqrt{2}},\\[3mm] \frac{2s}{n} & \mbox{, if } s> \frac{dn}{\sqrt{2}}. \end{cases}$$ Our results are based on a smoothing technique relating the degree deviation and the largest eigenvalue to low-dimensional non-linear optimization problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_14936 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Optimization Approach to Degree Deviation and Spectral Radius Rautenbach, Dieter Werner, Florian Combinatorics For a finite, simple, and undirected graph $G$ with $n$ vertices and average degree $d$, Nikiforov introduced the degree deviation of $G$ as $s=\sum_{u\in V(G)}\left|d_G(u)-d\right|$. Provided that $G$ has largest eigenvalue $λ$, minimum degree at least $δ$, and maximum degree at most $Δ$, where $0\leqδ<d<Δ<n$, we show $$s\leq \frac{2n(Δ-d)(d-δ)}{Δ-δ} \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mbox{and}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, λ\geq \begin{cases} \frac{d^2n}{\sqrt{d^2n^2-s^2}} & \mbox{, if } s\leq \frac{dn}{\sqrt{2}},\\[3mm] \frac{2s}{n} & \mbox{, if } s> \frac{dn}{\sqrt{2}}. \end{cases}$$ Our results are based on a smoothing technique relating the degree deviation and the largest eigenvalue to low-dimensional non-linear optimization problems. |
| title | An Optimization Approach to Degree Deviation and Spectral Radius |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2412.14936 |