Nonregular graphs of odd maximum degree with maximum spectral radius

Liangdong Fan; Liying Kang; Yaojun Chen

In the authors' words

Let $ρ (n, d)$ denote the maximum adjacency spectral radius among all connected nonregular graphs of order $n$ and maximum degree $d$ . A graph attaining this maximum is called an extremal graph. Liu [J. Combin. Theory Ser. B, 2024] determined the extremal graphs for $d = 3, 4$ and formulated two conjectures for general $d$ . For each fixed odd integer $d \geq 3$ , the conjectures assert that: (1) $n \to \infty lim n^{2} (d - ρ (n, d)) = (d - 1) π^{2} /4$ . (2) For all sufficiently large $n$ , the degree sequence of every extremal graph is $(d, \dots, d, d - 1)$ for odd $n$ and $(d, \dots, d, 1)$ for even $n$ . We prove the first conjecture for every fixed odd $d \geq 3$ and, more precisely, obtain the asymptotic expansion \[ \rho(n,d) =d-\frac{(d-1)\pi^2}{4n^2} +\frac{(d-1)^2\pi^2}{4n^3} +O_d(n^{-4}) \qquad(n\to\infty). \] We further prove the second conjecture for every fixed odd $d \geq 3$ .

Main resultThe abstract does not state a limitation.

Nonregular graphs of odd maximum degree with maximum spectral radius

In the authors' words

More on Combinatorics & discrete math that day

Thinning and sprinkling: from robust sampling to almost Hamiltonicity

Boolean threshold functions, neuron capacity, and memory retrieval

The Marcus-Minc Transform Inequality

The coarse Erd\H{o}s-P\'{o}sa theorem

A Combinatorial Proof of Hilton's Conjecture and Beyond