The real eigenvalues of the non-backtracking Laplacian
Let $G$ be a simple graph on $N$ nodes and $M$ edges, with minimum degree at least $2$. We prove that the non-backtracking Laplacian of $G$ has at least $2M-2N+2c+2b$ real eigenvalues, counted with algebraic multiplicity, where $c$ is the number of connected components of $G$ and $b$ is the number of bipartite ones. More precisely, at least $M-N+2c$ of them lie in $[0,1)$ and at least $M-N+2b$ lie in $(1,2]$. We show that the bound $2M-2N+2c+2b$ is sharp, and that a connected $d$-regular graph attains it if and only if it is strictly Ramanujan, i.e., every adjacency eigenvalue $μ\ne\pm d$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.02194
curl -X POST /api/v1/records/arxiv/2611.02194/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.02194/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'