Equality in Nikiforov's average-neighbour-degree bounds for A_α

For a graph without isolated vertices, Nikiforov bounded the spectral radius of $A_\alpha=\alpha D+(1-\alpha)A$ by the minimum and maximum of $\alpha d(v)+(1-\alpha)m(v)$, where $m(v)$ is the average degree of the neighbours of $v$. We study equality for connected, nonregular graphs and $0<\alpha<1$. Such a graph has at most one equality parameter; it is rational, belongs to $(0,1/2]$, and forces $A_\alpha$ to be singular. At $\alpha=1/2$ the graphs are precisely the nonregular semiregular bipartite graphs. We give an integral recognition criterion and a complete classification when exactly two degrees occur. Conversely, every rational number in $(0,1/2]$ occurs. For every $k\ge 2$ an explicit connected $2k$-vertex graph with $k$ distinct degrees attains equality at $\alpha=1/3$; thus no absolute bound on degree variety is possible. An exact isomorphism-class census through ten vertices, independently generated by nauty and checked with rational arithmetic, yields $599$ irregular cases at order ten. We distinguish proofs from finite computer certificates, and delimit the prior-art search rather than asserting publication novelty. The record holds the article (PDF) and a snapshot of its repository with the LaTeX source, the arXiv package, every certificate (programs, logs, SHA-256) and two independent literature audits. Provenance: ChatGPT research agents (OpenAI) wrote proofs, programs and the draft; Anthropic Claude, the lab's guide, checked the proofs line by line, re-derived the finite results independently (nauty, exact arithmetic) and checked every reference; the author takes responsibility. Text and data CC BY 4.0, code MIT.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-15
DOI
https://doi.org/10.5281/zenodo.24241526
Primary Topic
Graph theory and applications
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Equality in Nikiforov's average-neighbour-degree bounds for A_α

Aleksei Kudriashov
Zenodo (CERN European Organization for Nuclear Research)
Graph theory and applications
preprint

Equality in Nikiforov's average-neighbour-degree bounds for A_α

Aleksei Kudriashov
preprint en

Abstract

For a graph without isolated vertices, Nikiforov bounded the spectral radius of $A_\alpha=\alpha D+(1-\alpha)A$ by the minimum and maximum of $\alpha d(v)+(1-\alpha)m(v)$, where $m(v)$ is the average degree of the neighbours of $v$. We study equality for connected, nonregular graphs and $0<\alpha<1$. Such a graph has at most one equality parameter; it is rational, belongs to $(0,1/2]$, and forces $A_\alpha$ to be singular. At $\alpha=1/2$ the graphs are precisely the nonregular semiregular bipartite graphs. We give an integral recognition criterion and a complete classification when exactly two degrees occur. Conversely, every rational number in $(0,1/2]$ occurs. For every $k\ge 2$ an explicit connected $2k$-vertex graph with $k$ distinct degrees attains equality at $\alpha=1/3$; thus no absolute bound on degree variety is possible. An exact isomorphism-class census through ten vertices, independently generated by nauty and checked with rational arithmetic, yields $599$ irregular cases at order ten. We distinguish proofs from finite computer certificates, and delimit the prior-art search rather than asserting publication novelty. The record holds the article (PDF) and a snapshot of its repository with the LaTeX source, the arXiv package, every certificate (programs, logs, SHA-256) and two independent literature audits. Provenance: ChatGPT research agents (OpenAI) wrote proofs, programs and the draft; Anthropic Claude, the lab's guide, checked the proofs line by line, re-derived the finite results independently (nauty, exact arithmetic) and checked every reference; the author takes responsibility. Text and data CC BY 4.0, code MIT.

Zenodo (CERN European Organization for Nuclear Research)
Graph theory and applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon