Upper bounds of the second largest eigenvalue of graphs
Let $λ_i(G)$ denote the $i$-th largest eigenvalue of adjacency matrix of a graph $G$. Gerschgorin's Theorem indicates $λ_1(G)$ belongs to the largest disk, i.e., $λ_1(G)\leΔ_1(G)$, where $Δ_i(G)$ is the $i$-th largest degree of $G$. We show that $λ_2(G)$ lies in the second largest disk. That is, in detail, $$λ_2(G)<Δ_2(G)-\frac{1}{n^2}.$$ A classical theorem proved by Hong [\textit{Linear Algebra Appl.} 1988] states that $λ_1(G)\le\sqrt{2m-n+1}$ for a connected graph $G$ with $n$ vertices and $m$ edges, where the equality holds if and only if $G$ is a star $S_n$ or a complete graph $K_n$. We…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.11633
curl -X POST /api/v1/records/arxiv/2606.11633/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.11633/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'