PreprintarXiv licencearXiv
Degree sequences of spectrally extremal connected nonregular graphs with prescribed maximum degree: the dense case
Abstract
Let G be an n-vertex connected nonregular graph with maximum degree Δ that attains the maximum spectral radius. For 3≤Δ≤ n−2, Liu and Li (2008) conjectured that G has the degree sequence (Δ,…,Δ,δ) with δ<Δ as large as possible. In this paper, we study the dense case where Δ=n−k with k≥4 fixed and n sufficiently large. We prove that d(G)= (Δ,…,Δ, 1), & if $n$ is even and $k$ is odd; (Δ,…,Δ,Δ−1), & if $n$ is odd and $k$ is even; (Δ,…,Δ,2), & if $n$ and $k$ have the same parity.
Related
- Extremal spectral radius of nonregular graphs with a fixed odd maximum degree
- The maximum spectral radius of connected graphs with prescribed order and size
- Extremal Graphs with Prescribed Parameters for the Spectral Radius of Weighted Adjacency Matrices with Property P∗
- Counting connected multitype graphs with prescribed edge counts
- Sharp bounds and extremal structure of minimally strongly k-connected digraphs
BibTeX
@misc{huang2026degree,
title = {{Degree sequences of spectrally extremal connected nonregular graphs with prescribed maximum degree: the dense case}},
author = {Zejun Huang and Chenxi Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02272},
eprint = {2610.02272},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02272},
}
RIS
TY - UNPB
TI - Degree sequences of spectrally extremal connected nonregular graphs with prescribed maximum degree: the dense case
AU - Zejun Huang
AU - Chenxi Yang
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02272
UR - https://arxiv.org/abs/2610.02272
AB - Let G be an n-vertex connected nonregular graph with maximum degree Δ that attains the maximum spectral radius. For 3≤Δ≤ n−2, Liu and Li (2008) conjectured that G has the degree sequence (Δ,…,Δ,δ) with δ<Δ as large as possible. In this paper, we study the dense case where Δ=n−k with k≥4 fixed and n sufficiently large. We prove that d(G)= (Δ,…,Δ, 1), & if $n$ is even and $k$ is odd; (Δ,…,Δ,Δ−1), & if $n$ is odd and $k$ is even; (Δ,…,Δ,2), & if $n$ and $k$ have the same parity.
ER -