The saturated spectral radius for complete graphs
Abstract
A graph is Kr+1-saturated if it is Kr+1-free and adding any missing edge creates a copy of Kr+1. Kim, Kim, Kostochka, and O conjectured that Kr−1∨(n−r+1)K1 minimizes the spectral radius among all n-vertex Kr+1-saturated graphs. They proved the case r=2, and the cases r=3 and r∈{4,5} were subsequently established by Kim, Kostochka, O, Shi, and Wang, and by Wang and Hou, respectively. We settle the conjecture for all r≥3: if n≥ r+1 and G is an n-vertex Kr+1-saturated graph, then ρ(G)≥ (r−2+√((r−2)2+4(r−1)(n−r+1)))/2, with equality if and only if G≅ Kr−1∨(n−r+1)K1. We also prove O's local two-walk conjecture for every r≥2: ∑w∈ NG(v)dG(w) ≥ (r−2)dG(v)+(r−1)(n−r+1) (v∈ V(G)). If G has no universal vertex, the inequality holds with the additional term $(r-1)(r-2)$ on the right-hand side. This constant is best possible uniformly in n for every fixed r, and gives a strict improvement when r≥3. A corresponding spectral bound follows.
Related
- Spectral radius and edge-disjoint spanning trees of graphs with edge connectivity
- Asymptotic maximum spectral radius of nonregular graphs
- Extremal spectral radius of nonregular graphs with a fixed odd maximum degree
- Independence number, essential connectivity and the distance spectral radius of graphs
- Minimizing the spectral radius of unicyclic graphs with fixed order and dissociation number
BibTeX
@misc{chen2026saturated,
title = {{The saturated spectral radius for complete graphs}},
author = {Zhengbo Chen and Xiao-Dong Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.12612},
eprint = {2609.12612},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12612},
}
RIS
TY - UNPB
TI - The saturated spectral radius for complete graphs
AU - Zhengbo Chen
AU - Xiao-Dong Zhang
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.12612
UR - https://arxiv.org/abs/2609.12612
AB - A graph is K_r+1-saturated if it is K_r+1-free and adding any missing edge creates a copy of K_r+1. Kim, Kim, Kostochka, and O conjectured that K_r−1∨(n−r+1)K_1 minimizes the spectral radius among all n-vertex K_r+1-saturated graphs. They proved the case r=2, and the cases r=3 and r∈{4,5} were subsequently established by Kim, Kostochka, O, Shi, and Wang, and by Wang and Hou, respectively. We settle the conjecture for all r≥3: if n≥ r+1 and G is an n-vertex K_r+1-saturated graph, then ρ(G)≥ (r−2+√((r−2)^2+4(r−1)(n−r+1)))/2, with equality if and only if G≅ K_r−1∨(n−r+1)K_1. We also prove O's local two-walk conjecture for every r≥2: ∑_w∈ N_G(v)d_G(w) ≥ (r−2)d_G(v)+(r−1)(n−r+1) (v∈ V(G)). If G has no universal vertex, the inequality holds with the additional term $(r-1)(r-2)$ on the right-hand side. This constant is best possible uniformly in n for every fixed r, and gives a strict improvement when r≥3. A corresponding spectral bound follows.
ER -